## Miller-Rabin

Expand Messages
• Anyone know of a (freely-available) program for Windoze that implements the Miller-Rabin strong-pseudo-primality test, and works on an input file of
Message 1 of 13 , Jul 27, 2003
• 0 Attachment
Anyone know of a (freely-available) program for Windoze that implements the
Miller-Rabin strong-pseudo-primality test, and works on an input file of
expressions, one per line, a la PFGW?

(This would of course be a nice feature to have in PFGW itself:-)

Mike

[Non-text portions of this message have been removed]
• (Sunday, July 27, 2003 3:41 PM) ... This is a DERIVE function for Rabin-Miller test: RABIN_MILLER(m, a) := If (ITERATE(IF(k_ = 2 OR a_ = -1, [a_, k_],
Message 2 of 13 , Aug 14, 2003
• 0 Attachment
(Sunday, July 27, 2003 3:41 PM)
mikeoakes2@... <mikeoakes2@...> escribió:

> Anyone know of a (freely-available) program for Windoze that
> implements the Miller-Rabin strong-pseudo-primality test, and works
> on an input file of expressions, one per line, a la PFGW?
>
> (This would of course be a nice feature to have in PFGW itself:-)
>
> Mike
>

This is a DERIVE function for Rabin-Miller test:

RABIN_MILLER(m, a) :=
If (ITERATE(IF(k_ = 2 OR a_ = -1, [a_, k_], [MODS(a_^2, m), k_/2]), [a_,
k_], ITERATE([- ABS(MODS(a^o_, m)), (m - 1)/o_], o_, ITERATE(IF(MOD(m_, 2) =
1, m_, m_/2), m_, m - 1), 1))) SUB 1 = -1
true
false

Or in one line;

RABIN_MILLER(m, a) := IF((ITERATE(IF(k_ = 2 OR a_ = -1, [a_, k_],
[MODS(a_^2, m), k_/2]), [a_, k_], ITERATE([- ABS(MODS(a^o_, m)), (m -
1)/o_], o_, ITERATE(IF(MOD(m_, 2) = 1, m_, m_/2), m_, m - 1), 1))) SUB 1
= -1, true, false)

The function give true if m is a strong pseudoprime with basis a, and false
otherwise.

It can be use with the programming tools of DERIVE. By example:

m:=
2887148238050771212671429597130393991977609459279722700926516024197432303799
1527331163289831446392259419778031109293496555784189494417409338056151139799
9942154241693397290542371100275104208013496673175515285922696291677532547504
4445856101949404200039904432116776619949629539250452698719329070373564032273
7012784538991261203092448414947289768854060249767681220770716879381217098113
22297802059565867

SELECT(NOT RABIN_MILLER(m, k), k, SELECT(PRIME(n), n, 1, 300))

return a void vector (in 15.7 s in a P3-500), saying that m is a strong
pseudoprime in all prime basis less than 300 (althought actually it is
composite).

Best regards,

Ignacio Larrosa Cañestro
A Coruña (España)
ilarrosa@...
• It would be very very easy to write a program that calls PFGW and which performs a Miller-Rabin test. If anybody wants one, let me know. Regards, Paul.
Message 3 of 13 , Aug 14, 2003
• 0 Attachment
It would be very very easy to write a program that calls PFGW and which
performs a Miller-Rabin test. If anybody wants one, let me know.

Regards,

Paul.

__________________________________________________
Virus checked by MessageLabs Virus Control Centre.
• In a message dated 14/08/03 13:40:39 GMT Daylight Time, ... Please! And could it then go into the primeform files area? Cohen s Rabin-Miller algorithm (ACCANT,
Message 4 of 13 , Aug 14, 2003
• 0 Attachment
In a message dated 14/08/03 13:40:39 GMT Daylight Time,
Paul.Jobling@... writes:

> It would be very very easy to write a program that calls PFGW and which
> performs a Miller-Rabin test. If anybody wants one, let me know.
>

Please! And could it then go into the primeform files area?

Cohen's Rabin-Miller algorithm (ACCANT, p.422) uses /20/ randomly chosen
bases; wiould you do the same, or make it a parameter?

BTW I'm unclear whether PFGW's "137-PRP!" means the number is a /strong/
pseudo-prime to base 137, as per Cohen (ibid., p.422).
Anyone know?

Mike

[Non-text portions of this message have been removed]
• ... I m just looking at the code, and although it pulls the power of 2 out (as if it was going to use it for a SPRP test), if you run it it does a fermat PRP
Message 5 of 13 , Aug 14, 2003
• 0 Attachment
> BTW I'm unclear whether PFGW's "137-PRP!" means the number is
> a /strong/

I'm just looking at the code, and although it pulls the power of 2 out (as if
it was going to use it for a SPRP test), if you run it it does a fermat PRP
test:

pfgw -b2 -q999986341201 -f -s1 -e11

says 999986341201 is 2-PRP!, but

pfgw -b2 -q999986341201 -f -s1 -e17

shows that it isn't prime at all. But 999986341201 is not a strong pseudoprime
base 2. I imagine SPRP functionality could be put in PFGW quite easily?
Perhaps a new function similar to the existing gwPRP() is required. I'll have
a play with the code...

Regards,

Paul.

__________________________________________________
Virus checked by MessageLabs Virus Control Centre.
• Basic pfgw test is Fermat=weak, for speed. To strengthen this use -t. RTFriendlyM: A.3.4 F-Strong test This test is used when you use the -t option, and your
Message 6 of 13 , Aug 14, 2003
• 0 Attachment
Basic pfgw test is Fermat=weak, for speed.
To strengthen this use -t.
RTFriendlyM:
A.3.4 F-Strong test
This test is used when you use the -t option,
and your factors don't reach the magic 33.33%.
It is a strong-primality test, and gives more certainty
than a Fermat test, but still is NOT a proof!
d
• Thanks for that spot, David - that saved me some work getting grubby in the code. I ll knock something up right now... Regards, Paul.
Message 7 of 13 , Aug 14, 2003
• 0 Attachment
Thanks for that spot, David - that saved me some work getting grubby in the
code. I'll knock something up right now...

Regards,

Paul.

__________________________________________________
Virus checked by MessageLabs Virus Control Centre.
• In a message dated 14/08/03 15:04:30 GMT Daylight Time, ... Thanks for that reminder, David. However, it still seems that, to be able to say my number has
Message 8 of 13 , Aug 14, 2003
• 0 Attachment
In a message dated 14/08/03 15:04:30 GMT Daylight Time,

> To strengthen this use -t.
>
Thanks for that reminder, David.

However, it still seems that, to be able to say "my number has passed 10
Rabin-Miller tests", PFGW can't be used.

This is because Miller-Rabin expects bases b to be chosen randomly in (1,N);
and, although Cohen expects reasonably reliable results to be obtained by
using smaller bases than that (e.g. 32-bit), it still seems rather "iffy" to use
bases restricted to PFGW's 255 max.

I wonder how hard would it be to allow PFGW's bases to be (say) up to 31-bit,
rather than just 8-bit? (Given that after a few squarings the numbers PFGW is
deailing with are huge, I can't imagine that the 255 limit on the starting
value b plays a very central role in the coding.)

Mike

[Non-text portions of this message have been removed]
• ... I saw nothing in the code to indicate why the base is limited to 255, and numbers up to 2^31 ought to be possible, IMHO (after a quick glance at the code,
Message 9 of 13 , Aug 14, 2003
• 0 Attachment
> I can't imagine that the 255 limit on the starting value b
> plays a very central role in the coding

I saw nothing in the code to indicate why the base is limited to 255, and
numbers up to 2^31 ought to be possible, IMHO (after a quick glance at the

Regards,

Paul.

__________________________________________________
Virus checked by MessageLabs Virus Control Centre.
• In a message dated 14/08/03 15:04:30 GMT Daylight Time, ... I m still not entirely clear what that makes PFGW do... I have just run pfgw -b107 -f20 -t -l and
Message 10 of 13 , Aug 14, 2003
• 0 Attachment
In a message dated 14/08/03 15:04:30 GMT Daylight Time,

> A.3.4 F-Strong test
> This test is used when you use the -t option,
> and your factors don't reach the magic 33.33%.
> It is a strong-primality test, and gives more certainty
> than a Fermat test, but still is NOT a proof!
>

I'm still not entirely clear what that makes PFGW do...

I have just run
pfgw -b107 -f20 -t -l

and got the following screen output:-

Primality testing 16^12281-15^12281 [N-1, Brillhart-Lehmer-Selfridge]
trial factoring to 438355
Running N-1 test using base 7
Running N-1 test using base 19
Calling Brillhart-Lehmer-Selfridge with factored part 0.16%
16^12281-15^12281 is PRP! (997.280000 seconds)

Does this mean (a) that my "-b107" has been ignored, and (b) that PFGW has
done 2 /strong/ pseudo-primality tests with its own choice of random numbers (7
and 19) (selected hopefully with uniform probability from the range 2..255) as
bases?

If so, this would be an excellent basis for Rabin-Miller, provided the base
range was increased to 31 bits (say), as one could then simply repeat this
exercise the desired number of times.

Anyone know?

Mike

[Non-text portions of this message have been removed]
• The numbers are almost random : they are the first primes where kronecker(p,N) = -1. PFGW loops through the primes, as you can see if you put the same number
Message 11 of 13 , Aug 14, 2003
• 0 Attachment
The numbers are almost random : they are the first primes where kronecker(p,N)
= -1. PFGW loops through the primes, as you can see if you put the same number
into a file a few times then run PFGW against the file. Again, the 255 limit
appears to be arbitrary to me...

__________________________________________________
Virus checked by MessageLabs Virus Control Centre.
• ... numbers (7 ... as ... Not. If you rerun the test, exactly the same bases are used. And for a different input number, 84^12409-83^12409, the bases chosen
Message 12 of 13 , Aug 14, 2003
• 0 Attachment
> Does this mean (a) that my "-b107" has been ignored, and (b) that PFGW has
> done 2 /strong/ pseudo-primality tests with its own choice of random
numbers (7
> and 19) (selected hopefully with uniform probability from the range 2..255)
as
> bases?

Not.

If you rerun the test, exactly the same bases are used.

And for a different input number, 84^12409-83^12409, the bases chosen are
(always) 2, 11 and 29.

So they are chosen neither randomly, nor uniformly from 2..255.

So there is no way with PFGW of doing even a strong primality test to a
single specific base, much less a Rabin-Miller.

:-(

Mike

[Non-text portions of this message have been removed]
• The limit is scattered throughout the code. I believe that most of this limit is in the argument processing section. If this is changed, then we need a
Message 13 of 13 , Aug 14, 2003
• 0 Attachment
The "limit" is scattered throughout the code. I believe that most
of this limit is in the argument processing section.

If this is changed, then we need a SIGNIFICANT amount of testing
before releasing this as "production" code.

NOTE that I believe that the size of base WILL impact PFGW. I think
that it impacts the FFT, as it is a square-mult mod N. The mult is
not sure at what point this "small mult" starts getting too big, and
causing problems. Keep in mind that the small-mult issue is why
N+1 proving is such a thorn-bed of problems.

I am going to look into the "saving the .ini file" issue, and can
readily "modify" the code to allow up to 2^31 for the testing base.

That should be very easy.

If someone "really" wants Miller-Rabin, then what needs to be done,
is a new gw_millerrabin.cpp file needs created, that does the same
as gw_prp.cpp, but uses the MR algorithm. I can easily add new
plumbing to the command line ( -mr# where # is the number of "random"
2^31 miller rabin bases), and call this new code.

Jim.

--- In primeform@yahoogroups.com, "Paul Jobling" <Paul.Jobling@W...>
wrote:
> > I can't imagine that the 255 limit on the starting value b
> > plays a very central role in the coding
>
> I saw nothing in the code to indicate why the base is limited to
255, and
> numbers up to 2^31 ought to be possible, IMHO (after a quick
glance at the