Re: Frobenius test and GMP library

From: BRG (brg_at_nowhere.org)
Date: 12/24/04


Date: Fri, 24 Dec 2004 12:01:37 +0000

Cristiano wrote:
> Sisyphus wrote:
>
>>[rob@localhost frobenius]$ ./frobenius.exe 10
>>212697255460959188811228955285461874921
>>Performing 10 iterations of the frobenius probable prime test on
>>212697255460959188811228955285461874921....
>>
>>Probable prime with parameters
>>68874042992856834480547917601092539187,
>>53020279949960851054630937398442978906
>
> [...]
>
> I get the same!
>
> I don't know whether you have the time, but it would be very helpful to try
> this:
> you should change the lines
> mpz_urandomm(a, rand_state, N);
> mpz_urandomm(b, rand_state, N);
> with: a=a+1 and b=b+1 which should be
> mpz_add_ui(a, a, 1);
> mpz_add_ui(b, b, 1);
>
> Using that code, the primes 107, 32507 and 74471 are declared composites
> (which seems very strange to me). Do you get the same?

with this change I get a different result:

----------------------------------------
Performing 10 iterations of the frobenius probable prime test on 107....

Probable prime with parameters 1, 1
Probable prime with parameters 3, 3
Probable prime with parameters 9, 9
Probable prime with parameters 10, 10
Probable prime with parameters 11, 11
Probable prime with parameters 12, 12
Probable prime with parameters 19, 19
Probable prime with parameters 25, 25
Probable prime with parameters 30, 30
Probable prime with parameters 35, 35

107 appears to be prime.
----------------------------------------
Performing 10 iterations of the frobenius probable prime test on 32507....

Probable prime with parameters 1, 1
Probable prime with parameters 3, 3
Probable prime with parameters 9, 9
Probable prime with parameters 10, 10
Probable prime with parameters 12, 12
Probable prime with parameters 21, 21
Probable prime with parameters 26, 26
Probable prime with parameters 27, 27
Probable prime with parameters 28, 28
Probable prime with parameters 33, 33

32507 appears to be prime.
----------------------------------------
Performing 10 iterations of the frobenius probable prime test on 74471....

Probable prime with parameters 1, 1
Probable prime with parameters 2, 2
Probable prime with parameters 3, 3
Probable prime with parameters 15, 15
Probable prime with parameters 21, 21
Probable prime with parameters 30, 30
Probable prime with parameters 35, 35
Probable prime with parameters 37, 37
Probable prime with parameters 38, 38
Probable prime with parameters 45, 45

74471 appears to be prime.
----------------------------------------

    Brian Gladman



Relevant Pages

  • Re: Frobenius test and GMP library
    ... > Unfortunately I'm not able to install that library in my system, ... Performing 10 iterations of the frobenius probable prime test on ...
    (sci.crypt)
  • Re: Frobenius test and GMP library
    ... > Performing 10 iterations of the frobenius probable prime test on ...
    (sci.crypt)
  • Re: Frobenius test and GMP library
    ... > I found a GMP implementation of the Frobenius test: ... Performing 10 iterations of the frobenius probable prime test on ... Probable prime with parameters 68874042992856834480547917601092539187, ...
    (sci.crypt)