 mersenneforum.org > Math newbie question - finding small factors of very large numbers
 User Name Remember Me? Password
 Register FAQ Search Today's Posts Mark Forums Read 2006-03-23, 09:13   #1
NeoGen

Dec 2005

5410 Posts 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....   2006-03-23, 10:03 #2 Jushi   Sep 2005 UGent 22·3·5 Posts 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   2006-03-23, 12:47 #3 Fusion_power   Aug 2003 Snicker, AL 7×137 Posts 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   2006-03-23, 21:45 #4 NeoGen   Dec 2005 2·33 Posts 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. :)   2006-03-23, 21:49   #5
ewmayer
2ω=0

Sep 2002
República de California

2·5,813 Posts 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   2006-03-23, 21:50   #6
R.D. Silverman

Nov 2003

22×5×373 Posts 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.   2007-03-13, 00:02   #7
m_f_h

Feb 2007

43210 Posts Quote:
 Originally Posted by R.D. Silverman 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. ]   2007-03-13, 00:04   #8
m_f_h

Feb 2007

1101100002 Posts Quote:
 Originally Posted by Fusion_power All known factoring algorithms are in effect trivial.(...)
well, hum... for you maybe...  Thread Tools Show Printable Version Email this Page Similar Threads Thread Thread Starter Forum Replies Last Post Dr Sardonicus Number Theory Discussion Group 1 2017-07-17 11:55 devarajkandadai Miscellaneous Math 15 2012-05-29 13:18 georgelouis@mac Math 41 2011-01-25 21:06 Zeta-Flux Factoring 187 2008-05-20 14:38 NeoGen Software 8 2006-03-20 01:22

All times are UTC. The time now is 23:20.

Sun Apr 18 23:20:44 UTC 2021 up 10 days, 18:01, 0 users, load averages: 2.13, 1.84, 1.77

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.