mersenneforum.org  

Go Back   mersenneforum.org > Great Internet Mersenne Prime Search > Hardware > GPU Computing

Reply
 
Thread Tools
Old 2011-07-01, 01:28   #1
wblipp
 
wblipp's Avatar
 
"William"
May 2003
New Haven

23×5×59 Posts
Default 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
wblipp is offline   Reply With Quote
Old 2011-07-01, 02:04   #2
Christenson
 
Christenson's Avatar
 
Dec 2010
Monticello

5·359 Posts
Default

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?
Christenson is offline   Reply With Quote
Old 2011-07-04, 15:36   #3
wblipp
 
wblipp's Avatar
 
"William"
May 2003
New Haven

23·5·59 Posts
Default

Quote:
Originally Posted by Christenson View Post
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
wblipp is offline   Reply With Quote
Old 2011-07-04, 18:15   #4
Christenson
 
Christenson's Avatar
 
Dec 2010
Monticello

179510 Posts
Default

So, how do we efficiently determine if k*(4*128159)+1 divides 41^(4*128159)-1?
Christenson is offline   Reply With Quote
Old 2011-07-04, 21:11   #5
LiquidNitrogen
 
LiquidNitrogen's Avatar
 
Jun 2011
Henlopen Acres, Delaware

7×19 Posts
Default

Quote:
Originally Posted by Christenson View Post
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.
LiquidNitrogen is offline   Reply With Quote
Old 2011-07-04, 21:46   #6
science_man_88
 
science_man_88's Avatar
 
"Forget I exist"
Jul 2009
Dumbassville

26·131 Posts
Default

Quote:
Originally Posted by wblipp View Post
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 is offline   Reply With Quote
Old 2011-07-04, 21:48   #7
science_man_88
 
science_man_88's Avatar
 
"Forget I exist"
Jul 2009
Dumbassville

26×131 Posts
Default

Quote:
Originally Posted by science_man_88 View Post
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 is offline   Reply With Quote
Old 2011-07-04, 22:25   #8
science_man_88
 
science_man_88's Avatar
 
"Forget I exist"
Jul 2009
Dumbassville

26×131 Posts
Default

Quote:
Originally Posted by science_man_88 View Post
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 ?
science_man_88 is offline   Reply With Quote
Old 2011-07-05, 12:16   #9
science_man_88
 
science_man_88's Avatar
 
"Forget I exist"
Jul 2009
Dumbassville

26×131 Posts
Default

Quote:
Originally Posted by science_man_88 View Post
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 ?
science_man_88 is offline   Reply With Quote
Old 2011-07-05, 17:28   #10
Christenson
 
Christenson's Avatar
 
Dec 2010
Monticello

5×359 Posts
Default

Quote:
Originally Posted by LiquidNitrogen View Post
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!
Christenson is offline   Reply With Quote
Old 2011-07-05, 17:34   #11
science_man_88
 
science_man_88's Avatar
 
"Forget I exist"
Jul 2009
Dumbassville

203008 Posts
Default 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.
science_man_88 is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
Bases > 1030 and k's > CK gd_barnes Conjectures 'R Us 132 2021-01-09 05:58
k*b^n+/-1, Bases 271 and 11971 robert44444uk Math 26 2021-01-08 07:08
Numbers in Other Bases are Belong to Us Stargate38 Lounge 44 2020-10-24 11:33
Primeness of bases henryzz Conjectures 'R Us 15 2010-04-18 18:07
Different bases = different times? 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

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2021, Jelsoft Enterprises Ltd.

This forum has received and complied with 0 (zero) government requests for information.

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation.
A copy of the license is included in the FAQ.