- **Math**
(*https://www.mersenneforum.org/forumdisplay.php?f=8*)

- - **newbie question - finding small factors of very large numbers**
(*https://www.mersenneforum.org/showthread.php?t=5654*)

newbie question - finding small factors of very large numbersHaving first started a [URL="http://www.mersenneforum.org/showthread.php?t=5618"]thread on the software section[/URL] that ended up deviating to maths, I'll post my last question from it here.
This was the last post I got: [QUOTE=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.[/QUOTE] 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.... |

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

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. [url]http://www.utm.edu/research/primes/[/url] Fusion |

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

[QUOTE=Fusion_power]the number of operations required to factor via trial division makes it one of the most efficient for small numbers.[/QUOTE]
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=Jushi]a^b mod p is reasonable easy to compute, because you can reduce mod p at every step.[/QUOTE] 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. |

[QUOTE=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. :)[/QUOTE] Generally, in the context in which it arises within this forum, 'mod' is NOT an operator. It is an equivalence class. |

[quote=R.D. Silverman;76301]Generally, in the context in which it arises within this forum, 'mod' is NOT an operator. It is an equivalence class.[/quote]
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 [B]operator[/B] 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. :wink:] |

[quote=Fusion_power;76234]All known factoring algorithms are in effect trivial.(...)[/quote]
well, hum... for you maybe... |

All times are UTC. The time now is 03:05. |

Powered by vBulletin® Version 3.8.11

Copyright ©2000 - 2021, Jelsoft Enterprises Ltd.