Calculating powmod...

[David Cleaver]

Hello,

I'm interested in calculating "powmod"'s such as:
Mod(2^9182347891540, 9182347891541)
However, when I ran the function, it gave an error:
  ***   length (lg) overflow

Actually, I'm really interested to see if a number is a base 2 pseudoprime.  I
saw the ispseudoprime function, but that uses the strong test, and I just need
to know:
2^(n-1) == 1 (mod n)

I'm only going to be working with 64-bit inputs.  Is there some setting I need
to change in pari to be able to find out the above?  Or is there some function I
might have overlooked that performs that calculation?  Thanks for your time.

-David C.

[wdn]

Do

Mod(2, 9182347891541)^9182347891540

On Sun, 18 Oct 2009, David Cleaver wrote:

> Hello,
>
> I'm interested in calculating "powmod"'s such as:
>
> However, when I ran the function, it gave an error:
> ***   length (lg) overflow
>
> Actually, I'm really interested to see if a number is a base 2 pseudoprime.
> I saw the ispseudoprime function, but that uses the strong test, and I just
> need to know:
> 2^(n-1) == 1 (mod n)
>
> I'm only going to be working with 64-bit inputs.  Is there some setting I
> need to change in pari to be able to find out the above?  Or is there some
> function I might have overlooked that performs that calculation?  Thanks for
> your time.
>
> -David C.
>

[Bill Allombert-3]

On Sun, Oct 18, 2009 at 11:20:51AM -0500, David Cleaver wrote:
> Hello,
>
> I'm interested in calculating "powmod"'s such as:
> Mod(2^9182347891540, 9182347891541)
> However, when I ran the function, it gave an error:
>  ***   length (lg) overflow

Of course because PARI cannot compute 2^9182347891540.
You should compute with the class of 2 in in Z/9182347891541Z, i.e.
Mod(2, 9182347891541).  In that case you get:

? Mod(2, 9182347891541)^9182347891540
%1 = Mod(7569093976632, 9182347891541)

Cheers,
Bill.

[David Cleaver]

Bill Allombert wrote:

> On Sun, Oct 18, 2009 at 11:20:51AM -0500, David Cleaver wrote:
>> Hello,
>>
>> I'm interested in calculating "powmod"'s such as:
>> Mod(2^9182347891540, 9182347891541)
>> However, when I ran the function, it gave an error:
>>  ***   length (lg) overflow
>
> Of course because PARI cannot compute 2^9182347891540.
> You should compute with the class of 2 in in Z/9182347891541Z, i.e.
> Mod(2, 9182347891541).  In that case you get:
>
> ? Mod(2, 9182347891541)^9182347891540
> %1 = Mod(7569093976632, 9182347891541)
>
> Cheers,
> Bill.
>

Thank you very much for this answer.

Also, is there a way to print out timing information at the end of a program?  I
know that when a "program" I've written finishes, I can do a ## to see how long
it took to run.  But, I'd like to somehow put that command into the program.
When I tried "##" or "##;", it said "unexpected character(s)" and pointed to
right after the "##".

-David C.

[Karim Belabas-4]

* David Cleaver [2009-10-19 07:25]:
> Also, is there a way to print out timing information at the end of a
> program?  I know that when a "program" I've written finishes, I can do a ##
> to see how long it took to run.  But, I'd like to somehow put that command
> into the program. When I tried "##" or "##;", it said "unexpected
> character(s)" and pointed to right after the "##".

## is a "keyboard shortcut", only valid in the command-line gp interpreter.

Have a look at gettime() for a more flexible equivalent.

You may also set a timer on by default : default(timer, 1) in a program,
or even timer = 1 in your .gprc

Cheers,

    K.B.
--
Karim Belabas, IMB (UMR 5251)  Tel: (+33) (0)5 40 00 26 17
Universite Bordeaux 1          Fax: (+33) (0)5 40 00 69 50
351, cours de la Liberation    http://www.math.u-bordeaux1.fr/~belabas/
F-33405 Talence (France)       http://pari.math.u-bordeaux1.fr/  [PARI/GP]
`