Other Bases?

[wblipp]

Is there any plan for GPU trial factoring for a^n-1 when a is not 2?

Oddperfect has a few long standing uses for this (a=41 a=127 a=157 and others)

http://home.earthlink.net/~oddperfec...TrialFactoring

William

[Christenson]

wb:
Since you are the supplier of our OBD page, the truthful answer is no, there is no such plan that anyone has discussed....but it sounds to me like there should be one. The large amount of GPU firepower is only going to take GIMPS proper, or even OBD, so far. I see a few bumps in the road, none of them unsurmountable:
1) I need to finish what I am doing in terms of automating responses to the Primenet server.
2) The sieving part that finds candidate factors needs to move from the CPU to the GPU.
3) Whoever is programming it needs to understand the algorithm, and how it differs from the current ones that decide on whether 2^n-1 is divided by a potential factor. They then need to program it.
4) i see a need for a P-1 program on GPUs. At least one of the potential people to carry out step 3 (myself) is interested in doing this.

mfaktc, on the outer levels,is not a hard or large program. At the risk of distracting me, why don't you explain to me (and quite possibly Oliver) what it is we are attempting to TF, which candidates we can eliminate by theorem, and how to decide whether a candidate is a factor. If I read you correctly, the second line says we are trying to factor 41^(2 * 128159)-1, and the third line says we are trying to factor 41^(2^2 * 128159)-1 => 41^(4*128159)-1, correct?

[wblipp]

Originally Posted by Christenson

If I read you correctly, the second line says we are trying to factor 41^(2 * 128159)-1, and the third line says we are trying to factor 41^(2^2 * 128159)-1 => 41^(4*128159)-1, correct?

Yes, you understand correctly. When dealing with composite exponents the algebraic factors can get messy and are not addressed here, but probably do not matter for our purposes. It is possible that a factor found for one exponent actually belongs to a smaller exponent, but this is easily determined afterwards. These issues also happen with the base 2, but it is even rarer that people want to trial factor a composite exponent in that base. Even here prime exponent are most interesting - the composite exponents are searched when we fail to find two factors in the prime exponents.

Like in the base 2, all factors will be k*exponent+1. When the exponent is odd, k must be even.

[Christenson]

So, how do we efficiently determine if k*(4*128159)+1 divides 41^(4*128159)-1?

[LiquidNitrogen]

Originally Posted by Christenson

So, how do we efficiently determine if k*(4*128159)+1 divides 41^(4*128159)-1?

Well 41^(4*128159)-1 always ends in 0.

[science_man_88]

Originally Posted by wblipp

Is there any plan for GPU trial factoring for a^n-1 when a is not 2?

Oddperfect has a few long standing uses for this (a=41 a=127 a=157 and others)

http://home.earthlink.net/~oddperfec...TrialFactoring

William

well I came up with a trail factor code in PARI based on:

http://www.mersenne.org/various/math.php and it works for base 2 but i realized over night how to expand it to base 4 or use it to test 2^(2p+1)-1 in less multiplications squaring and mods but higher numbers faster could we not change this to base 41 ? because it should work no ? so if 1 multiply by 41 on top of squaring. I can check it out for you if you want.

[science_man_88]

Originally Posted by science_man_88

well I came up with a trail factor code in PARI based on:

http://www.mersenne.org/various/math.php and it works for base 2 but i realized over night how to expand it to base 4 or use it to test 2^(2p+1)-1 in less multiplications squaring and mods but higher numbers faster could we not change this to base 41 ? because it should work no ? so if 1 multiply by 41 on top of squaring. I can check it out for you if you want.

actually maybe it's ^41 which is harder.

[science_man_88]

Originally Posted by science_man_88

well I came up with a trail factor code in PARI based on:

http://www.mersenne.org/various/math.php and it works for base 2 but i realized over night how to expand it to base 4 or use it to test 2^(2p+1)-1 in less multiplications squaring and mods but higher numbers faster could we not change this to base 41 ? because it should work no ? so if 1 multiply by 41 on top of squaring. I can check it out for you if you want.

want me to prove something based on the TF there for any base b based on the binary form of a number ?

the general form for what that TF does:

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

is:

              Remove   Optional   
    Square        top bit  mul by b            mod x
    ------------  -------  -------------  ------
    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

for any base b because it raises the base b to to exponent p and mods by x along the way. I'm guessing this general form is known well ?

[science_man_88]

Originally Posted by science_man_88

want me to prove something based on the TF there for any base b based on the binary form of a number ?

the general form for what that TF does:



is:

              Remove   Optional   
    Square        top bit  mul by b            mod x
    ------------  -------  -------------  ------
    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

for any base b because it raises the base b to to exponent p and mods by x along the way. I'm guessing this general form is known well ?

anyone care for me to try a few examples ?

[Christenson]

Originally Posted by LiquidNitrogen

Well 41^(4*128159)-1 always ends in 0.

That's a weak statement. The general form, of which I am sure the odd perfect folks are aware, is as follows:

for any integer a >1, and any integer p>=1,
(a+1)^p - 1 is congruent to 0 mod a.

To prove it, use the binomial expansion of (a+1)^p

In our case, a=40, so 5 and 2^3 divide 41^p - 1
I assume they want to find some non-trivial factors, too!

[science_man_88]

Remove Optional 
Square top bit mul by b=4 mod x =47
------------ ------- ------------- ------
1*1 = 1 1 0111 1*4= 4                      4
4*4 = 16 0 111 no 16 
16*16 = 256 1 11 256*4 =1024 37 
37*37 = 1369 1 1369*4 = 5476 24 
24*24 = 576 1 576*4 = 2304 1

so 4^23 =2^46=1 mod 47

changing the last one up by a multiple of 2 brings it back to base 2:

Remove Optional 
Square top bit mul by b=4 mod x =47
------------ ------- ------------- ------
1*1 = 1 1 0111 1*4= 4 4
4*4 = 16 0 111 no 16 
16*16 = 256 1 11 256*4 =1024 37 
37*37 = 1369 1 1369*4 = 5476 24 
24*24 = 576 1 576*8 = 4608 2

okay so 2^47 = 2 mod 47 which goes back to 2^47-1 = 1 mod 47.

okay I know I'd be better formatting it first.