## RE: [PrimeNumbers] Re: x-prp numbers generation

Expand Messages
• ... It s educational to work it out. I recommend all those cutting their number-theoretical teeth on the list to attempt to give a proof. Here s a quick demo
Message 1 of 16 , Jan 10, 2006
--- fyatim <fyatim@...> wrote:
> Thanks for the clarification.
>
> Indeed, I found out that, by definition, Yat(x,p)=Phi(2p,x)=(x^p+1)/(x+1),
> but I can not find where is written:
>
> - That Yat(x,p) (or Phi(2p,x)) generates always x-PRP numbers
> - A demonstration of this fact.

It's educational to work it out. I recommend all those cutting their
number-theoretical teeth on the list to attempt to give a proof.

Here's a quick demo in Pari/GP:

? print(factor(subst(polcyclo(2*29),x,2))[,1]~)
[59, 3033169]
? znorder(Mod(2,59))
%10 = 58
? znorder(Mod(2,3033169))
%11 = 58

? print(factor(subst(polcyclo(2*71),x,2))[,1]~)
[56409643, 13952598148481]
? znorder(Mod(2,56409643))
%12 = 142
? znorder(Mod(2,13952598148481))
%13 = 142

What you see above always happens, guaranteed. The proof needn't be any longer
than the above demonstrations.

> Also, I'm not stating that Yat(x,p) is more likely to be prime than any
> other number in the same cyclotomic form, But I'm saying that is more likely
> to be prime than any other odd number chosen in N,

For each p there's an associated probability boost due to excluded factors.
Most boosts are fairly modest. The highest I've seen is about 11, for my own
PIES project, but there p is not prime. (p does not need to be prime for the
above to hold. In fact you don't even need to use '2p', any cyclotomic
polymonial works.)

Phil

() ASCII ribbon campaign () Hopeless ribbon campaign
/\ against HTML mail /\ against gratuitous bloodshed

[stolen with permission from Daniel B. Cristofani]

__________________________________________________
Do You Yahoo!?
Tired of spam? Yahoo! Mail has the best spam protection around
http://mail.yahoo.com
• Using Yat(2, 83339), PFGW find out a Fermat and Lucas PRP with 25,088 digits PFGW Version 1.2.0 for Windows [FFT v23.8] Output logging to file pfgw.out
Message 2 of 16 , Jan 10, 2006
Using Yat(2, 83339), PFGW find out a Fermat and Lucas PRP with 25,088 digits

PFGW Version 1.2.0 for Windows [FFT v23.8]

Output logging to file pfgw.out

Primality testing (2^(83339)+1)/3 [N-1/N+1, Brillhart-Lehmer-Selfridge]

Running N-1 test using base 2

Running N+1 test using discriminant 5, base 1+sqrt(5)

Calling N+1 BLS with factored part 0.03% and helper 0.02% (0.10% proof)

(2^(83339)+1)/3 is Fermat and Lucas PRP! (306.2205s+0.0022s)

Done.

_____

From: fyatim [mailto:fyatim@...]
Sent: Tuesday, January 10, 2006 10:39 PM
To: 'Phil Carmody'
Subject: RE: [PrimeNumbers] Re: x-prp numbers generation

Thanks for the clarification.

Indeed, I found out that, by definition, Yat(x,p)=Phi(2p,x)=(x^p+1)/(x+1),
but I can not find where is written:

- That Yat(x,p) (or Phi(2p,x)) generates always x-PRP numbers

- A demonstration of this fact.

Also, I'm not stating that Yat(x,p) is more likely to be prime than any
other number in the same cyclotomic form, But I'm saying that is more likely
to be prime than any other odd number chosen in N, or may be than other
cyclotomic form such as Mersenne or Fermat forms...

Thanks

Faysal

_____

Behalf Of Phil Carmody
Sent: Tuesday, January 10, 2006 1:54 PM
Subject: [PrimeNumbers] Re: x-prp numbers generation

From: "fyatim" <fyatim@...>
> I would like to submit a method to generate x-PRP numbers.
>
> Not without some pain, but I believe this should be submitted to the
> community.
>
> I confirm (a demonstration is under process) that : for every p Prime and
> x>1, the polynomial form :
>
> Yat(x,p)=x^(p-1)-x^(p-2)+x^(p-3)-.-x+1 is x-PRP ..

This is just Phi(2p,2).
Phi(n,b) is a notorious way of generating b-PRPs.
It may be b-PRP, but it's no more likely to be prime than any
other number of the same cyclotomic form.

Phil

() ASCII ribbon campaign () Hopeless ribbon campaign
/\ against HTML mail /\ against gratuitous bloodshed

[stolen with permission from Daniel B. Cristofani]

__________________________________________
Yahoo! DSL - Something to write home about.
Just \$16.99/mo. or less.
dsl.yahoo.com

Unsubscribe by an email to: primenumbers-unsubscribe@yahoogroups.com
The Prime Pages : http://www.primepages.org/

_____

* To unsubscribe from this group, send an email to:

* Your use of Yahoo! Groups is subject to the Yahoo!

_____

[Non-text portions of this message have been removed]
• From: Alan Eliasen ... But these aren t just shown to be 2-PRP, they re 2-PRP by construction. I m not saying you re wrong, it s
Message 3 of 16 , Jan 11, 2006
From: "Alan Eliasen" <eliasen@...>
> fyatim wrote:
> > The number of 2-PRP numbers is infinite, I agree. But, searching for Primes
> > in a group of 2-PRPs numbers should give you more chance (Probability) to
> > find a Prime than searching directly in N . What do you thing ???
>
> I agree with you, especially for large numbers. Let's say we're using a
> strong pseudoprime (SPRP) test. In the worst case, it declares composite
> numbers to be possibly prime at worst 1/4 of the time, and this worst-case
> number is achieved rarely. So, at the very worst, you're 4 times more likely
> to find primes among numbers that have already been shown to be 2-PRP.

But these aren't just "shown to be" 2-PRP, they're 2-PRP by construction. I'm
not saying you're wrong, it's just that I require a more convincing argument,
one that takes into account the fact the fact that these numbers are
constructed 2-PRPs.

I've not read all your references, I shall see if I can grab them and give them

Phil

() ASCII ribbon campaign () Hopeless ribbon campaign
/\ against HTML mail /\ against gratuitous bloodshed

[stolen with permission from Daniel B. Cristofani]

__________________________________________________
Do You Yahoo!?
Tired of spam? Yahoo! Mail has the best spam protection around
http://mail.yahoo.com
• ... This and many larger are known since 2000. http://www.primenumbers.net/prptop/prptop.php says: (2^374321+1)/3 112682 H.&R. Lifchitz 12/2000 (2^269987+1)/3
Message 4 of 16 , Jan 11, 2006
fyatim wrote:

> Using Yat(2, 83339), PFGW find out a Fermat and Lucas PRP with 25,088 digits
>
> (2^(83339)+1)/3 is Fermat and Lucas PRP! (306.2205s+0.0022s)

This and many larger are known since 2000.

(2^374321+1)/3 112682 H.&R. Lifchitz 12/2000
(2^269987+1)/3 81274 H.&R. Lifchitz 10/2000
(2^267017+1)/3 80380 H.&R. Lifchitz 09/2000
(2^141079+1)/3 42469 H.&R. Lifchitz 09/2000
(2^138937+1)/3 41824 H.&R. Lifchitz 09/2000
(2^127031+1)/3 38240 H.&R. Lifchitz 09/2000
(2^117239+1)/3 35292 H.&R. Lifchitz 09/2000
(2^95369+1)/3 28709 Richard McIntosh 07/2000
(2^83339+1)/3 25088 Richard McIntosh 07/2000
(2^42737+1)/3 12865 Richard McIntosh 07/2000