mersenneforum.org  

Go Back   mersenneforum.org > Great Internet Mersenne Prime Search > Math

Reply
 
Thread Tools
Old 2006-03-23, 09:13   #1
NeoGen
 
Dec 2005

2×33 Posts
Default newbie question - finding small factors of very large numbers

Having first started a thread on the software section that ended up deviating to maths, I'll post my last question from it here.

This was the last post I got:
Quote:
Originally Posted by ewmayer
If you can write the number in the form a^b+c with a and c reasonably small, trial-factoring is a very attractive approach.
So, I was just wondering, what is the name of that little formula, or to what theorem/conjecture/something else is it related to, so I can google for it. Googling for "a^b+c" gives next to nothing related to maths....
NeoGen is offline   Reply With Quote
Old 2006-03-23, 10:03   #2
Jushi
 
Jushi's Avatar
 
Sep 2005
UGent

22·3·5 Posts
Default

1) There is Fermat's Little Theorem, stating that a^b = a^(b mod (p-1)) mod p, whenever p is prime.

Therefore,
p is a factor of a^b + c
if and only if
a^b + c = 0 mod p
if and only if
a^(b mod (p-1)) + c = 0 mod p

2) a^b mod p is reasonable easy to compute, because you can reduce mod p at every step.

Last fiddled with by Jushi on 2006-03-23 at 10:12
Jushi is offline   Reply With Quote
Old 2006-03-23, 12:47   #3
Fusion_power
 
Fusion_power's Avatar
 
Aug 2003
Snicker, AL

7·137 Posts
Default

All known factoring algorithms are in effect trivial.

As the size of the number being factored increases, the amount of time required to factor it eventually becomes impossible with current computers and algorithms.

The "holy grail" of mathematics would be a highly efficient algorithm.

That said, the number of operations required to factor via trial division makes it one of the most efficient for small numbers.

A good online place to start would be Chris Caldwell's prime pages.

http://www.utm.edu/research/primes/

Fusion
Fusion_power is offline   Reply With Quote
Old 2006-03-23, 21:45   #4
NeoGen
 
Dec 2005

2·33 Posts
Default

Thanks guys. :)

For a while I was confused about the "mod" operator, as english is not my native language, and many times I had seen referenced "mod" as the remainder of a division, and it didn't make sense here.
But I dug out a bit more and found out that in number theory is a little different than that. :)
NeoGen is offline   Reply With Quote
Old 2006-03-23, 21:49   #5
ewmayer
2ω=0
 
ewmayer's Avatar
 
Sep 2002
Rep├║blica de California

3·7·19·29 Posts
Default

Quote:
Originally Posted by Fusion_power
the number of operations required to factor via trial division makes it one of the most efficient for small numbers.
Or for searching for modest-sized factors of very large numbers. In fact, if the number in question is sufficiently large (currently that means roughly a gigabyte or so, depending on precisely what kind of hardware one has access to), trial division (typically not effected via direct division, as that would be horrendously slow) is the *only* viable approach, since it is the only algorithm that need only do arithmetic modulo the factor candidates being tried (assuming the number to be factored has a convenient algebraic form - that's where the n = a^b + c thing comes in), rather than modulo the full number to be factored.

Quote:
Originally Posted by Jushi
a^b mod p is reasonable easy to compute, because you can reduce mod p at every step.
And being able to write the number to be factored in this kind of exponential form allows one to make use of the fact that a^b can be calculated very efficiently via a binary powering ladder.

For instance, say you want to see whether q = 178021379228511215367151 is a factor of n = 2^(2^31-1) - 1. Writing n = a^b + c we have a = 2, b = 2^31-1, c = -1. If q divides n, then we have that a^b == -c (mod q), so for our example we need to calculate a^b modulo q and see if the result = 1. In preparation for the modular binary powering (MBP) we note that the exponent b = 1111111111111111111111111111111 (31 ones) in binary. In our case we'll use the left-to-right variant of MBP - right-to-left can also be done, but if a is much smaller than q, left-to-right is more efficient, since we only need to do a single modular squaring at each step, accompanied by a scalar multiply-by-a if the bit of b we just processed = 1.

We initialize:

0) x = 2; (this takes care of the leftmost ones bit of b)

and then do

1) x = 2*x^2 (mod q)

precisely 30 times - note that in our case we have a multiply-by-2 every time we do step (1) since all the remaining bits of b are ones. This gives the following set of intermediate residues (values of x at the end of each step):

2
8
128
32768
2147483648
9223372036854775808
163838671770271031914265
15940493260465229871950
3241280417152100506399
158358996707726756723277
61129290337189275533363
54871195260911358933739
9178815705087946934352
166758140328565769436466
4093137255045902533677
10947296531501990810385
149772099971681362871577
29533071583478194672304
34389519377677041015199
88402528940368234107936
163767147554222421378281
167215834886684418792371
174051265515813627491088
110277565498222136928568
39908442523855154406594
116089841645424907791200
102552639853224147450969
167119800630617206330752
136650683570408535064649
8241756301268948440054
1

...and the result == 1 mod q, so q = 178021379228511215367151 is indeed a factor of n = 2^(2^31-1) - 1.

Last fiddled with by ewmayer on 2006-03-23 at 21:58
ewmayer is offline   Reply With Quote
Old 2006-03-23, 21:50   #6
R.D. Silverman
 
R.D. Silverman's Avatar
 
Nov 2003

22·5·373 Posts
Default

Quote:
Originally Posted by NeoGen
Thanks guys. :)

For a while I was confused about the "mod" operator, as english is not my native language, and many times I had seen referenced "mod" as the remainder of a division, and it didn't make sense here.
But I dug out a bit more and found out that in number theory is a little different than that. :)
Generally, in the context in which it arises within this forum, 'mod' is
NOT an operator. It is an equivalence class.
R.D. Silverman is offline   Reply With Quote
Old 2007-03-13, 00:02   #7
m_f_h
 
m_f_h's Avatar
 
Feb 2007

24·33 Posts
Default

Quote:
Originally Posted by R.D. Silverman View Post
Generally, in the context in which it arises within this forum, 'mod' is NOT an operator. It is an equivalence class.
In theory this is true, but as e.g. seen in ewmayer's previous post, mostly it is in fact used as an operator (operating on both sides of the equation). I'd estimate to > 95% the percentage of occurances of "a = b (mod c)" where the r.h.s. b is a number less than c and one can resonably assume that the author thinks of the l.h.s. as "a mod c".

Also, "mod" is not an equivalence class, at best " = (mod c)" is an equivalence relation
(or "=" means "element of" and "b (mod c)" is then indeed an equivalence class, so "mod" is the operator that associates to the first operand (b) the equivalence class modulo cZ, i.e. the multiples of the second operand (c)).

[Sorry for the unqualified post, just to tease Prof. Dr. R.D.S. ]
m_f_h is offline   Reply With Quote
Old 2007-03-13, 00:04   #8
m_f_h
 
m_f_h's Avatar
 
Feb 2007

24×33 Posts
Default

Quote:
Originally Posted by Fusion_power View Post
All known factoring algorithms are in effect trivial.(...)
well, hum... for you maybe...
m_f_h is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
A note on small factors of Fermat numbers Dr Sardonicus Number Theory Discussion Group 1 2017-07-17 11:55
Mersenne prime factors of very large numbers devarajkandadai Miscellaneous Math 15 2012-05-29 13:18
New method of finding large prime numbers georgelouis@mac Math 41 2011-01-25 21:06
Finding factors of cunningham-like numbers Zeta-Flux Factoring 187 2008-05-20 14:38
newbie question - testing primality of very large numbers NeoGen Software 8 2006-03-20 01:22

All times are UTC. The time now is 07:40.

Thu Dec 3 07:40:30 UTC 2020 up 3:51, 0 users, load averages: 1.01, 0.98, 0.96

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2020, 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.