- --- fyatim <fyatim@...> wrote:
> Thanks for the clarification.

It's educational to work it out. I recommend all those cutting their

>

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

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

For each p there's an associated probability boost due to excluded factors.

> 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,

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

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'

Cc: 'primenumbers@yahoogroups.com'

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

Any further clarifications from your part could be very helpful..

Thanks

Faysal

_____

From: primenumbers@yahoogroups.com [mailto:primenumbers@yahoogroups.com] On

Behalf Of Phil Carmody

Sent: Tuesday, January 10, 2006 1:54 PM

To: primenumbers@yahoogroups.com

Subject: [PrimeNumbers] Re: x-prp numbers generation

From: "fyatim" <fyatim@...>> I would like to submit a method to generate x-PRP numbers.

This is just Phi(2p,2).

>

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

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/

_____

YAHOO! GROUPS LINKS

* Visit your group "primenumbers

<http://groups.yahoo.com/group/primenumbers> " on the web.

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

primenumbers-unsubscribe@yahoogroups.com

<mailto:primenumbers-unsubscribe@yahoogroups.com?subject=Unsubscribe>

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

<http://docs.yahoo.com/info/terms/> Terms of Service.

_____

[Non-text portions of this message have been removed] - From: "Alan Eliasen" <eliasen@...>
> fyatim wrote:

But these aren't just "shown to be" 2-PRP, they're 2-PRP by construction. I'm

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

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

a read.

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 - fyatim wrote:

> Using Yat(2, 83339), PFGW find out a Fermat and Lucas PRP with 25,088 digits

This and many larger are known since 2000.

>

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

http://www.primenumbers.net/prptop/prptop.php says:

(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

See also http://www.research.att.com/~njas/sequences/A000978

That page should say they are only prp's above n=14479.

I will submit a comment about it.

By the way, that site has been redesigned since I last saw it.

Primes on form (2^p+1)/3 are called Wagstaff primes.

I see no reason to believe this form should be more likely to be

prime than other numbers without small factors.

Sieving other forms can easily generate numbers without small factors.

--

Jens Kruse Andersen