20060323, 09:13  #1  
Dec 2005
54_{10} 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:


20060323, 10:03  #2 
Sep 2005
UGent
2^{2}·3·5 Posts 
1) There is Fermat's Little Theorem, stating that a^b = a^(b mod (p1)) 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 (p1)) + 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 20060323 at 10:12 
20060323, 12:47  #3 
Aug 2003
Snicker, AL
1111000000_{2} 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 
20060323, 21:45  #4 
Dec 2005
2·3^{3} 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. :) 
20060323, 21:49  #5  
∂^{2}ω=0
Sep 2002
República de California
11743_{10} Posts 
Quote:
Quote:
For instance, say you want to see whether q = 178021379228511215367151 is a factor of n = 2^(2^311)  1. Writing n = a^b + c we have a = 2, b = 2^311, 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 lefttoright variant of MBP  righttoleft can also be done, but if a is much smaller than q, lefttoright is more efficient, since we only need to do a single modular squaring at each step, accompanied by a scalar multiplybya 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 multiplyby2 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^311)  1. Last fiddled with by ewmayer on 20060323 at 21:58 

20060323, 21:50  #6  
"Bob Silverman"
Nov 2003
North of Boston
2^{2}×3×7×89 Posts 
Quote:
NOT an operator. It is an equivalence class. 

20070313, 00:02  #7  
Feb 2007
2^{4}×3^{3} Posts 
Quote:
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. ] 

20070313, 00:04  #8 
Feb 2007
110110000_{2} Posts 

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  20170717 11:55 
Mersenne prime factors of very large numbers  devarajkandadai  Miscellaneous Math  15  20120529 13:18 
New method of finding large prime numbers  georgelouis@mac  Math  41  20110125 21:06 
Finding factors of cunninghamlike numbers  ZetaFlux  Factoring  187  20080520 14:38 
newbie question  testing primality of very large numbers  NeoGen  Software  8  20060320 01:22 