Sorry, an error occurred while loading the content.

## 14275Re: Modification of PFGW

Expand Messages
• 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
time.

Jim.

--- In primenumbers@yahoogroups.com, Cletus Emmanuel <cemmanu@y...>
wrote:
> 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
member?....
> ---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