Re: ERH - MSW primality test

From: Phil Carmody (thefatphil_demunged_at_yahoo.co.uk)
Date: 11/15/04 

Date: 15 Nov 2004 02:50:19 +0200

Phil Carmody <thefatphil_demunged@yahoo.co.uk> writes:
> Note that C&P has the 2.ln(n)^2 expression as a bound for
> Strong Pseudoprimility tests. The paper doesn't even use
> such strong tests, it's basically half-way between a
> Fermat Test and a Euler Test (+/-1, don't care which one).

Just for reference (and you probably know this) your n is not
even a 2-SPRP!

The Euler test yields +1, but one step earlier gives
sqrt(1) == 120096492 (mod n)
not +/-1.

So real Miller (see dissertation's 3.11 = C&P 3.4.1) knocks this
composite on the head immediately!

Phil 

-- 
They no longer do my traditional winks tournament lunch - liver and bacon. 
It's just what you need during a winks tournament lunchtime to replace lost 
... liver.   -- Anthony Horton, 2004/08/27 at the Cambridge 'Long Vac.'

Relevant Pages

  • Re: Excercices
    ... > Phil Carmody wrote: ... Not lynx. ... [press right arrow] ... They no longer do my traditional winks tournament lunch - liver and bacon. ...
    (alt.lang.asm)
  • Re: Expected average cycle length...
    ... > Phil Carmody wrote: ... surprising, condition that it was a PRP not a PRF being talked about. ... They no longer do my traditional winks tournament lunch - liver and bacon. ...
    (sci.crypt)
  • Re: GAS assembly quirks
    ... Phil Carmody writes: ... > god alone knows why) ... registers, and it compiled fine. ... They no longer do my traditional winks tournament lunch - liver and bacon. ...
    (alt.lang.asm)