newbie question - finding small factors of very large numbers

[NeoGen]

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:

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....

[Jushi]

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.

[Fusion_power]

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

[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. :)

[ewmayer]

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.

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.

[R.D. Silverman]

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.

[m_f_h]

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. ]

[m_f_h]

Originally Posted by Fusion_power

All known factoring algorithms are in effect trivial.(...)

well, hum... for you maybe...