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

14275Re: Modification of PFGW

Expand Messages
  • jim_fougeron
    Dec 25, 2003
    • 0 Attachment
      I will make a short reply here (even though this might be a little
      off topic).

      1. the primeform group (which supports OpenPFGW at a "user" level)
      can be found at http://groups.yahoo.com/group/primeform/

      2. Testing for b^((N-1)/2)%N vs b^(N-1)%N saves only 1 squaring.
      In you trivial sample below (47) you list that PFGW would loop 46
      times. You might want to take a quick refresher on algorithms for
      exponentation (Knuth volume 2 is a good reference, as are dozens of
      other tomes).

      The exponentation used in PFGW (or any math package) only performs a
      squaring (with possible multiplication) per each "bit" of the number.

      So, testing 3*10^1000000+1 requires only 3321929 "steps", and NOT
      10^1000000 steps (there is a HUGE difference between the two).
      However, performing the test you have listed (b^((n-1)/2))%n would
      require 3321928 steps, thus for a non-trivial change to the code and
      logic of the exponentation, you save an extremely trivial amount of


      --- In primenumbers@yahoogroups.com, Cletus Emmanuel <cemmanu@y...>
      > Mike,
      > Let me first say, I am very ignorant when it come to the working
      of PFGW, I will admit. However, I am very much willing to learn....
      > Yes, I do realize that it is one less iteration. However, if we
      can let PFGW evaluate
      > ((N-1)/2), coupled with the loop I speak of. I said "a basic for
      loop" for two reasons:
      > 1) because it is (I really think) simple
      > 2) My C codes are very rusty and the loop is written in Basic
      > By no means, am I asking to write Basic codes in PFGW.
      > Now, let me give an example of this code... if PFGW were to check
      47 for 2-PRP, based on how this group have explained it to me, it
      would have to check 2^46%47 (which would be 46 iterations) to see if
      it equal 1. In the basic loop I speak of, it would take 5 loops
      (ofcourse 47 is viewed as a Carol number - a special case). And
      that's why I would like for the program to be optimized for
      Carol/Kynea numbers.
      > Also, can you direct me to the Primeform group? How do I become a
      > ---Cletus Emmanuel
      > 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
      > ---------------------------------
      > 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