Other Bases?

[Ken_g6]

I think there was some confusion here. I believe William is talking about:

if TF factors (41*43)^P-1, then the same factor either factors 41^P-1 or 43^P-1.

On the other hand, Christenson is talking about TF-ing 41^P-1, then using that to more quickly do the same TF-ing on 41^(K*P)-1, but I think that's trivially factored by K and P, isn't it? So what about doing the same TF-ing on 41^(K+P)-1?

Finally, I'm talking about cycling through trial factors TF, and solving for P in 41^P mod TF, using a discrete logarithm algorithm. srsieve uses BSGS, but I think Pollard Rho might be simpler to implement, especially on GPUs.

[Christenson]

Originally Posted by Ken_g6

I think there was some confusion here. I believe William is talking about:

if TF factors (41*43)^P-1, then the same factor either factors 41^P-1 or 43^P-1.

On the other hand, Christenson is talking about TF-ing 41^P-1, then using that to more quickly do the same TF-ing on 41^(K*P)-1, but I think that's trivially factored by K and P, isn't it? So what about doing the same TF-ing on 41^(K+P)-1?

Finally, I'm talking about cycling through trial factors TF, and solving for P in 41^P mod TF, using a discrete logarithm algorithm. srsieve uses BSGS, but I think Pollard Rho might be simpler to implement, especially on GPUs.

If you start working on the above, you may get to implementation well before I do.....

What I was noticing was that William had cited a web page where the factors of both
41^(large #)-1 and 41^(large # * small factor)-1 were being sought, where small factor was numbers like 2^3, etc.

In addition to the trivial observation that 40 is a factor of both of those, I notice that any factor of 41^(large #)-1 is also a factor of 41^(large # * factor, small or large)-1.

So the proposal was, for many at least pseudoprime factor candidates FC, to calculate 41^(large #) mod FC, and then check for some range of exponents (from 1 to small #) to see if it was a small root of unity.

**************
I'm not sure which is "better". I am pretty sure my proposal is easy to code.

William????

[Ken_g6]

Wikipedia gives the identity



I imagine this extends for numbers other than 2, which would mean P must be prime for B^P-1 to be prime.

Edit: Wikipedia also has a proof that A^P-1, where P>1, is never prime for A != 2!

[Christenson]

B^P-1 can only be prime if B is 2; otherwise, do the binomial expansion, subtract 1, and notice that all terms divide by B-1.
For example:
((40+1)^3 -1)/40 = -1 + 1 + 3*40 + 3*40^2 + 40^3 = 3 + 3*40 + 40^2.

[science_man_88]

Originally Posted by Christenson

B^P-1 can only be prime if B is 2; otherwise, do the binomial expansion, subtract 1, and notice that all terms divide by B-1.
For example:
((40+1)^3 -1)/40 = -1 + 1 + 3*40 + 3*40^2 + 40^3 = 3 + 3*40 + 40^2.

the TF given at http://www.mersenne.org/various/math.php can be expanded to any base using the binary version of the exponent and multiplier of Base instead of 2.

               Remove   Optional   
    Square        top bit  mul by 2       mod 47
    ------------  -------  -------------  ------
    1*1 = 1       1  0111  1*2 = 2           2
    2*2 = 4       0   111     no             4
    4*4 = 16      1    11  16*2 = 32        32
    32*32 = 1024  1     1  1024*2 = 2048    27
    27*27 = 729   1        729*2 = 1458      1

becomes:

               Remove   Optional   
    Square        top bit  mul by b       mod 47
    ------------  -------  -------------  ------
    1*1 = 1       1  0111  1*b = b           2
    2*2 = 4       0   111     no             4
    4*4 = 16      1    11  16*b = 32        32
    32*32 = 1024  1     1  1024*b = 2048    27
    27*27 = 729   1        729*b = 1458      1

the one gimps uses is just a b=2 scenario.

all do an example ( b=41):

      Remove   Optional   
    Square        top bit  mul by b       mod 47
    ------------  -------  -------------  ------
    1*1 = 1       1  0111  1*41 = 41           41
    41*41 = 1681       0   111     no             36
    36*36 = 1296      1    11  1296*41 = 53136       26
    26*26 = 676  1     1  676*41 = 27716    33
    33*33 = 1089   1        1089*41 = 44649      46

see if it worked out:

(20:10)>(41^23)%47
%88 = 46

[Christenson]

SM88...indeed, it works great...the question is, given the similarity of some of the numbers to be TF'ed, is if they should be TF'ed together....to save some computing work...

[science_man_88]

Originally Posted by Christenson

SM88...indeed, it works great...the question is, given the similarity of some of the numbers to be TF'ed, is if they should be TF'ed together....to save some computing work...

well if we used exponent x I know ways to change this using laws of exponentiation to search using binary(x) for factors of things like exponent t*x+1 as well it just takes a few changes. so we could test all exponent with a small group of exponents changed to binary.

[wblipp]

Originally Posted by Christenson

Or can you give me a slightly more concrete example?

From the example in Post #25, Zetaflux is interested in finding two large prime factors of 719^(2^2 * 3 * 183925013)-1. We already know the following algebraic factors:

719^(2*3*183925013)-1
719^(2*3*183925013)+1
719^(4*183925013)-1
719^(3*183925013)-1
719^(3*183925013)+1
719^(2*183925013)-1
719^(2*183925013)+1
719^183925013-1
719^183925013+1

We furthermore know that for each of these, the factors are of the form k*exponent+1. Hence you COULD design a system to separately test each of these possibilities.

HOWEVER, you get the same result with less complexity if test

719^(2^2*3*183925013)-1

testing for divisors of the form k*183925013+1

Any factors of any of the numbers will be found by this method. When factors are found, Zetaflux will want to know which of the above composites is the smallest that the found factors divide - that is an easy problem.


To be even more concrete, from this page:

http://oddperfect.org/FermatQuotients.html


Zetaflux was interested in two large factors of 97^(8*4794006457)-1

Testing this for factors of the form 2k*4794006457+1, we found

44469203895133
3394156571557

which were easily determined to be divisors of
97^4794006457+1
97^(2*4794006457)+1

Is there more I need to clarify?

[Christenson]

No, the post, even without the link, is crystal clear.

The right computation, for the 719s given above, is, I think:
FC = 2k*183925013+1, k prime, (or at least pseudo-prime)
M=719^183925013 mod FC
FC is "good" if any of M, M^2, M^3...M^12 is congruent to +/-1 mod FC

Do I need to eliminate FCs which are multiples of factors of 718? I know that no FC will be a direct multiple of 718, which is itself an algebraic factor.

Let me know if this is the right thing or not....

[wblipp]

Originally Posted by Christenson

The right computation, for the 719s given above, is, I think:
FC = 2k*183925013+1, k prime, (or at least pseudo-prime)
M=719^183925013 mod FC
FC is "good" if any of M, M^2, M^3...M^12 is congruent to +/-1 mod FC

Do I need to eliminate FCs which are multiples of factors of 718? I know that no FC will be a direct multiple of 718, which is itself an algebraic factor.

Let me know if this is the right thing or not....

You need only check M^12. If M, M^2, or M^3 is +1/-1, then so is M^12.

I was further proposing testing M^12 for only +1. If the user is interested in the possibility of M^12=-1, he would test M^24.

Direct multiples of 718 are even, and thus will not be generated by 2kp+1. Even when this isn't true, such candidates will usually be eliminated the pseudoprime step.

[Christenson]

Originally Posted by wblipp

You need only check M^12. If M, M^2, or M^3 is +1/-1, then so is M^12.

I was further proposing testing M^12 for only +1. If the user is interested in the possibility of M^12=-1, he would test M^24.

Direct multiples of 718 are even, and thus will not be generated by 2kp+1. Even when this isn't true, such candidates will usually be eliminated the pseudoprime step.

Would a user be interested in M^3,M^5,M^7,M^11 all together?
[or would they have to ask for M^(3*5*7*11), which is going to take 15*7*11 = 1155 (> 2^10) --> 11 additional steps, as opposed to simply looking at M, M^2, M^3...M^12, which also takes 11 additional steps]

Can you give me an idea of the population of likely requests? I don't have the sophistication/experience to know which case I should be optimising for, beyond the fact that whoever is using this is going to need to search automatically for the interesting Ms.....as there are going to be a lot of them. The corollary of this is that this search will need to happen inside the same processor that generates the Ms, otherwise we'll be getting into huge communications delays.