Pseudo prime tests

[bodrato at mail.dm.unipi.it]

Ciao,

Il Gio, 14 Giugno 2012 2:41 pm, Torbjorn Granlund ha scritto:
> bodrato at mail.dm.unipi.it writes:

>   I wrote a kind of implementation for the Lucas-Selfridge test, it

> Cool.  I suppose I need to read more about the maths to fully admire
> your work.  :-)

I plainly implemented the formulas from Wikipedia. Using the binary method
to compute Q^t and the two numbers U_t and V_t.
I should have recycled the powers of Q to obtain a M-R test in parallel,
but I used U_t and V_t only... So, there is nothing to be admired :-/

> That depends on the perspective.  If for a set of k integers, the test
> is correct for all but f, I'd argue that a random integer from the set
> have a likelihood of f/k to trigger a test failure.

We have to choose the perspective. Should we give the probability that:
- given a number (even maliciously chosen) the test fail, or
- the test fail on random numbers?

If we choose the second, checking the parity only gives the first 1/2...

>   I'd add 2b. Run Lucas (with fixed parameters? like MR with base 2?).

> Perhaps.  It is not clear to me that that would be an improvement since

> (2) we will not be able to make stronger promises of the likelihood of

Right, but Lucas adds another 1/4 (more or less), as a Miller-Rabin. We
haven't any proof that it is better, but there are authors that claim that
Lucas might be "complementary" and not "orthogonal". We might increase the
chances that the test is stronger than our promises :-D


>   An observation. My implementation of Lucas, detects if a number is in
>   the form 2^s-1; it does not exploit the fact... but it shouldn't be
>   difficoult to switch to Lucas-Lehmer, then give a "definitely" answer.
>
> We could also identify 2^s and return 0 (when s != 1).  :-)

I don't say that we should detect many special forms, but that Mersenne
numbers gets detected by my code, as a side effect. For example we might
test the primality of the exponent, to speed-up composite detection. I
attach a new code with this implemented. As you can see with a diff, I
only added an else branch.

Regards,
m

-- 
http://bodrato.it/papers/
-------------- next part --------------
A non-text attachment was scrubbed...
Name: stronglucasselfridge_p.c
Type: text/x-csrc
Size: 4511 bytes
Desc: not available
URL: <http://gmplib.org/list-archives/gmp-devel/attachments/20120614/5d0c9df4/attachment.bin>