mersenneforum.org Other Bases?
 Register FAQ Search Today's Posts Mark Forums Read

 2011-07-01, 01:28 #1 wblipp     "William" May 2003 New Haven 23×5×59 Posts Other Bases? 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
 2011-07-01, 02:04 #2 Christenson     Dec 2010 Monticello 5·359 Posts 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?
2011-07-04, 15:36   #3
wblipp

"William"
May 2003
New Haven

23·5·59 Posts

Quote:
 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.

Last fiddled with by wblipp on 2011-07-04 at 15:38

 2011-07-04, 18:15 #4 Christenson     Dec 2010 Monticello 179510 Posts So, how do we efficiently determine if k*(4*128159)+1 divides 41^(4*128159)-1?
2011-07-04, 21:11   #5
LiquidNitrogen

Jun 2011
Henlopen Acres, Delaware

7×19 Posts

Quote:
 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.

2011-07-04, 21:46   #6
science_man_88

"Forget I exist"
Jul 2009
Dumbassville

26·131 Posts

Quote:
 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.

2011-07-04, 21:48   #7
science_man_88

"Forget I exist"
Jul 2009
Dumbassville

26×131 Posts

Quote:
 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.

2011-07-04, 22:25   #8
science_man_88

"Forget I exist"
Jul 2009
Dumbassville

26×131 Posts

Quote:
 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:

Quote:
 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:

Code:
              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 ?

2011-07-05, 12:16   #9
science_man_88

"Forget I exist"
Jul 2009
Dumbassville

26×131 Posts

Quote:
 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: Code:  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 ?

2011-07-05, 17:28   #10
Christenson

Dec 2010
Monticello

5×359 Posts

Quote:
 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!

 2011-07-05, 17:34 #11 science_man_88     "Forget I exist" Jul 2009 Dumbassville 203008 Posts none of you probably care. But ... Code: 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: Code: 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.

 Similar Threads Thread Thread Starter Forum Replies Last Post gd_barnes Conjectures 'R Us 132 2021-01-09 05:58 robert44444uk Math 26 2021-01-08 07:08 Stargate38 Lounge 44 2020-10-24 11:33 henryzz Conjectures 'R Us 15 2010-04-18 18:07 roger Information & Answers 1 2007-04-25 14:35

All times are UTC. The time now is 00:16.

Wed Jan 20 00:16:15 UTC 2021 up 47 days, 20:27, 0 users, load averages: 2.50, 2.72, 2.72