Factoring program need help

Citrix · 2005-09-14, 22:47

I am looking for a program to trial factors numbers of the form a^b-1 and a^b+1, I am just interested in small factors. But a and b can extend to 2^32.
Does anyone have such a program or can prime95 be used or can LUigi's program be modified. OR can some one write a program.

Citrix

rogue · 2005-09-14, 23:51

The software you use depends upon a and b. Are either one fixed? Is there a relationship between a and b, such as a=b or a=2b? Are there ranges for a and/or b?

Citrix · 2005-09-15, 00:47

I am intrested in a^a+1 and a^a-1 right now, but I might want to work on other numbers in the future.
See
http://www.mersenneforum.org/showthr...newpost&t=4631

Citrix

Citrix · 2005-09-15, 01:28

a^a-1/a-1 and a^a+1/a+1 with 'a' prime.

alpertron · 2005-09-15, 12:31

In order to factor these numbers you should first check whether they have an Aurifeuillian factorization. In that way you crack the number in two chunks of about the same size.

For example, using my applet I found in less than 2 minutes (the big prime primality test time) that 211^211 + 1 =

2 ^ 2 x 53 x 213533 x 579407 x 46 406435 349739 x 88 525902 868092 421204 996157 621808 213014 430014 887767 787743 522503 906242 008512 782503 486118 533512 785146 944720 236634 198021 697609 675117 546179 913655 039907 037975 383744 841612 298481 628994 717733 023250 894952 744819 673093 770812 846672 408282 803763 x 246130 193292 807764 953953 811304 965911 556521 721296 069333 564773 431021 734072 101197 483068 800029 533398 117737 335047 117109 076449 501012 926929 386556 396394 504228 200372 562141 045456 832277 553849 852215 431729 464846 531770 078309 936467 281716 435936 267853 (Composite)

Notice the big prime number that could not be found if the Aurifeuillian process were not done.

alpertron · 2005-09-15, 12:54

In general, for p prime, there is an Aurifeuillian factorization for:

p^[i]p[/i] + 1 if p mod 4 = 3
p^[i]p[/i] - 1 if p mod 4 = 1

Citrix · 2005-09-15, 18:45

Thanks alot, that reduces alot of work for me.

Citrix · 2005-09-16, 00:53

Rogue,

Would you be willing to write a sieving software?

http://www.mersenneforum.org/showthr...1131#post61131

Citrix

Citrix · 2005-09-16, 02:31

Quote:

Originally Posted by Citrix

Rogue,

Would you be willing to write a sieving software?

http://www.mersenneforum.org/showthr...1131#post61131

Citrix

Just hold on this one, I might not need a sieve.
Thanks anyway.

Citrix

2005-09-14, 22:47	#1
Citrix Jun 2003 1605₁₀ Posts	Factoring program need help I am looking for a program to trial factors numbers of the form a^b-1 and a^b+1, I am just interested in small factors. But a and b can extend to 2^32. Does anyone have such a program or can prime95 be used or can LUigi's program be modified. OR can some one write a program. Citrix

2005-09-15, 00:47	#3
Citrix Jun 2003 645₁₆ Posts	I am intrested in a^a+1 and a^a-1 right now, but I might want to work on other numbers in the future. See http://www.mersenneforum.org/showthr...newpost&t=4631 Citrix Last fiddled with by Citrix on 2005-09-15 at 00:57

Similar Threads
Thread	Thread Starter	Forum	Replies	Last Post
The P-1 factoring CUDA program	firejuggler	GPU Computing	753	2020-12-12 18:07
A small factoring program	Yamato	Factoring	2	2007-11-21 23:29
Where is a factoring program?	Siemelink	Software	2	2006-01-10 20:30
Factoring Program	HarvestMoon	Factoring	9	2005-09-15 01:42
Factoring program	ET_	Programming	3	2003-11-25 02:57

2005-09-14, 23:51	#2
rogue "Mark" Apr 2003 Between here and the 2×7²×71 Posts	The software you use depends upon a and b. Are either one fixed? Is there a relationship between a and b, such as a=b or a=2b? Are there ranges for a and/or b?

2005-09-15, 01:28	#4
Citrix Jun 2003 3×5×107 Posts	a^a-1/a-1 and a^a+1/a+1 with 'a' prime.

2005-09-15, 12:31	#5
alpertron Aug 2002 Buenos Aires, Argentina 10111010100₂ Posts	In order to factor these numbers you should first check whether they have an Aurifeuillian factorization. In that way you crack the number in two chunks of about the same size. For example, using my applet I found in less than 2 minutes (the big prime primality test time) that 211^211 + 1 = 2 ^ 2 x 53 x 213533 x 579407 x 46 406435 349739 x 88 525902 868092 421204 996157 621808 213014 430014 887767 787743 522503 906242 008512 782503 486118 533512 785146 944720 236634 198021 697609 675117 546179 913655 039907 037975 383744 841612 298481 628994 717733 023250 894952 744819 673093 770812 846672 408282 803763 x 246130 193292 807764 953953 811304 965911 556521 721296 069333 564773 431021 734072 101197 483068 800029 533398 117737 335047 117109 076449 501012 926929 386556 396394 504228 200372 562141 045456 832277 553849 852215 431729 464846 531770 078309 936467 281716 435936 267853 (Composite) Notice the big prime number that could not be found if the Aurifeuillian process were not done.

2005-09-15, 12:54	#6
alpertron Aug 2002 Buenos Aires, Argentina 2²×373 Posts	In general, for p prime, there is an Aurifeuillian factorization for: p^[i]p[/i] + 1 if p mod 4 = 3 p^[i]p[/i] - 1 if p mod 4 = 1

2005-09-15, 18:45	#7
Citrix Jun 2003 3105₈ Posts	Thanks alot, that reduces alot of work for me.

2005-09-16, 00:53	#8
Citrix Jun 2003 3×5×107 Posts	Rogue, Would you be willing to write a sieving software? http://www.mersenneforum.org/showthr...1131#post61131 Citrix