Loading ...
Sorry, an error occurred while loading the content.
 

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

Expand Messages
  • Phil Carmody
    ... 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
    • fyatim
      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'
        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.
        >
        > 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/





        _____

        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]
      • Phil Carmody
        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
          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
        • Jens Kruse Andersen
          ... 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.
            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
          Your message has been successfully submitted and would be delivered to recipients shortly.