(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@...