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

14288Re: [PrimeNumbers] Re: Modification of PFGW

Expand Messages
  • Cletus Emmanuel
    Dec 30, 2003
    • 0 Attachment
      Guys,
      Again I say, I am not as smart as some of you guys, but I do understand a PRP of primality test. After all, I am a mathematician. All I am saying is that I don't know the process that PFGW is taking in checking for PRP's. I do know that if we want to check for b^(N-1)%N, we let N-1 = d*2^t, where d is odd. Then do b^d%N and squaring from there.
      Now, a Carol number, because of it form C = [4^k - 2^(k+1) - 1] can easily be tested. If we define E = (C-1)/2 and let b = 2, from Euler we get 2^E == 1 mod C if C is prime. Because E is always odd for a Carol number we would calculate 2^E and then do one squaring. I don't know of any other faster way of getting there. We can quickly calculate (N+1)/2 = 2^k[2^(k-1) - 1]. There are more squaring, and I think that calculating 2^E will be a lot faster. As a matter of FACT, it will take 2k loops to calculate 2^E.

      Here is the full test (be forewarned...this is Programming in Basic codes)...
      ---------------------------------------------
      d=2
      for i = 2 to k
      d = d^2==Ck; read C sub k, where Ck = (2^k-1)^2 - 2
      Next i
      If odd(d) then d = d+Ck
      d = d/2
      For J = 1 to k
      d = d^2==Ck
      Next j
      if d = 2 then Ck is 2-EPRP
      -------------------------------------------------------------
      I am going further to conjecture that if d = 2 in the last line of the test then Ck is prime. In short, I am saying that Ck is prime iff Ck divides C(k+E).

      I may still be wrong about everything above in terms of making PFGW more efficient, but guys show me the way, don't knock me down. I have always thought of this group as a group that I can learn a lot from. In any event, if there is anyone that can implement this into PFGW please let me know ASAP. I know that i am saying, think that I just can't explain it fully. If I can prove my conjecture, then finding a new worlds largest prime will be as easy as testing for 2-EPRP, which in the case of Carol or Kynea numbers would take about 2*k steps....

      Just a little note: Carol and Kynea primes are more densely populated than Mersenne in a given range from 1 to 'n'. So far, there are 32 Carol and 40 Kynea for k-values <= 100,000.
      grostoon <grostoon@...> wrote:
      Hi all,

      I agree with you that for huge N, computing b^((N-1)/2)%N instead of
      b^(N-1)%N result in a negligible time gain.

      But what if you consider the accuracy of the test itself rather than
      the time it takes : why just doing a basic fermat prp test ?
      Maybe I'm missing something but I believed that a strong probable
      prime test (rabin-miller's prp test) was more accurate than the
      simple fermat's test (and not much difficult to implement). Am I
      wrong ?

      Jean-Louis.


      --- In primenumbers@yahoogroups.com, mikeoakes2@a... wrote:
      > In a message dated 23/12/03 22:00:27 GMT Standard Time,
      cemmanu@y...
      > writes:
      >
      >
      > > I've been asking of Chris Nash ( I presume that he is very busy)
      to modify
      > > PFGW to check for Carol/Kynea numbers for a while now....Can
      anyone modify
      > > PFGW to do b^((N-1)/2)%N rather than b^(N-1)%N? There is even a
      faster way (I
      > > think) I can let it calculate b^((N-1)/2)%N (with a basic for
      loop)....
      > >
      >
      >
      > You do realize, do you, that for N = 2^1000000-1 (for example), "to
      do
      > b^((N-1)/2)%N rather than b^(N-1)%N" takes 999999 rather than
      1000000 FFTs; in other
      > words, there is a negligible difference in execution time.
      >
      > PFGW is already a highly optimized and efficient program; so if you
      think
      > simple ideas involving "a basic for loop" are going to make it
      faster, you are
      > probably mistaken.
      >
      > The proper forum for this discussion is really the primeform group,
      or, for
      > implementation issues, openpfgw.
      >
      > -Mike Oakes
      >
      >
      > [Non-text portions of this message have been removed]



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




      Yahoo! Groups SponsorADVERTISEMENT


      ---------------------------------
      Yahoo! Groups Links

      To visit your group on the web, go to:
      http://groups.yahoo.com/group/primenumbers/

      To unsubscribe from this group, send an email to:
      primenumbers-unsubscribe@yahoogroups.com

      Your use of Yahoo! Groups is subject to the Yahoo! Terms of Service.



      ---------------------------------
      Do you Yahoo!?
      Free Pop-Up Blocker - Get it now

      [Non-text portions of this message have been removed]
    • Show all 19 messages in this topic