Re: ERH - MSW primality test

From: Mack (macckone_at_a_nospamjunk123_ol.com)
Date: 11/14/04 

Date: Sun, 14 Nov 2004 21:43:57 GMT

On Sun, 14 Nov 2004 17:27:28 GMT, "Cristiano"
<cristiano.pi@NSquipo.it> wrote:

>I read the interesting Sebastian Wedeniwski's paper "Primality Tests on
>Commutator Curves" which can be found here:
>http://w210.ub.uni-tuebingen.de/dbt/volltexte/2001/420/pdf/dissertation.pdf
>
>At page 107 he explains the ERH - Miller-Selfridge-Weinberger Test to check
>the primality of a number:
>
>n is an integer number > 8;
>
>if a^[(n-1)/2] != +/- 1 (mod n) for some prime number a
>a < 1.5 ln(n)^2 - 8.8 ln(n) +13
>
>then n is composite, otherwise n is prime.
>
>Assuming that the Extended Riemann Hypothesis is true, the above algorithm
>is correct (please, see page 107 for a better explanation).
>
>My problem:
>n = 366652201 = 461 x 691 x 1151
>a < 422.777787
>
>a^3378856 (mod 366652201) is always = 1 for all the 82 primes from 2 to 421.
>This means that n is declared prime by the test.
>And I get the same for a=431, 433, 439, 443, 449 and 457.
>461 is the first prime base which gives a residue != +/- 1 (showing that n
>is composite).
>
>Any comment?
>
>Cristiano
>
errr ... shouldn't that be a^183326100 mod 366652201

and is there an english version of the above paper?

Leslie 'Mack' McBride
remove text between _ marks to respond via e-mail

Relevant Pages

  • Re: EFFICIENCY: PRIME TEST vs PRIME GENERATOR
    ... > Let's suppose we have an algorithm that will take a positive ... > For example, the USUAL test runs on odd numbers, checking for primality. ... > The time it takes to prove one such number is either composite or prime is ... > you DON'T use every partition, you might require very large exponents. ...
    (sci.math)
  • Re: Primes algorithm
    ... > method which is generally used, as far as I know, is the Miller-Rabin ... > algorithm, ... > that a given number is composite, then it is definitely composite; ... A number is prime with a probability equal to either 0 or to 1. ...
    (sci.crypt)
  • Re: Towards a Formula for Primes
    ... did the OP prove that this algorithm always makes primes? ... which are either composite, or not necessarily prime ... it certainly comports to Big Peak Oil's statistics -- ...
    (sci.math)
  • Re: Probabalistic algorithms.
    ... >Hashing is typically just an optimisation. ... all the hash does is guarantee that given some ... >hard to factor the composite into its two prime factors. ... >algorithm that's dfaster than brute force factorisation, ...
    (comp.lang.pascal.delphi.misc)
  • Re: Riemann Hypothesis and P vs NP
    ... However I did check to see if the algorithm ... call it the Strong Pseudo Prime test) will prove an N composite. ... Prime testing ... We've got several P-time 's but they arn't as interesting as and ...
    (comp.theory)