Finding Factors

It seems that the Easy Math Puzzles thread has pulled all of the serious mathoids out of the woodwork, so I figure that somebody may have some insight into this problem.

How do you factor a number into primes quickly if the largest prime factor is itself quite large?

Example: (10^211 - 1) / 9 - i.e. the 211-digit positive integer where all 211 digits are 1s - has two prime factors:
692,624,557,324,389,620,662,782,322,677,336,711,138,108,482,588,281,739,734,375,570,506,492,391,931,849,524,636,731,866,879
and 1,604,204,037,181,898,492,842,452,177,634,233,120,825,494,895,604,445,254,059,369,227,570,068,074,354,992,595,031,636,365,651,567,169,241,873,842,145,514,809

How did anyone possibly find either one of those in any reasonable length of time (other than "well, we found the other one first")?

And while I'm asking...what's the preferred method for primality testing (with 100% certainty) of non-Mersenne primes?

I find this topic very interesting, but don't know that I'll have much of value to contribute.

I thought there was no foolproof quick way to find prime factors. That, I thought, was why cryptography and cryptocurrencies work -- that it takes a LONG time to find large prime factors. I hear there are shortcuts that can help find prime factors, but they don't always work.

I'd say that's my two cents, but I would be asking too much.

Quote: ThatDonGuy

It seems that the Easy Math Puzzles thread has pulled all of the serious mathoids out of the woodwork, so I figure that somebody may have some insight into this problem.

How do you factor a number into primes quickly if the largest prime factor is itself quite large?

There is no easy answer. One of the greatest unsolved problems of all time. The unknown P=NP and Riemann Hypothesis are both linked to this. Essentially you are looking for a log(N) solution (number of steps is approximately the number of digits in the number). P=NP says roughly that checking a solution is correct should take the same time as finding a solution and that is the golden egg folks are looking for. So if P=NP was ever proven then such an algorithm would have to exist, even if no one knew it. RH is also related, as it gives very strong results about the distribution of primes. Mersenne Primes have this property, for example, that you can prove N=2^p -1 is a prime or composite in O(log(N)) time, though finding a factor if they are not prime is not solved. The general area of study is known as Sieve Theory and of course Wikipedia has a ton on this problem.

My own experience with this dates to my graduate school days at the University of Arizona. John Brillhart was a professor there. He and George Seligman were setting some early records looking for large primes and developing factoring methods. It was a very hot area of study at the time as computer security was in its infancy. At any rate, the FBI (or maybe it was the CIA) was trying to seize his research and claim it was a national security risk (it probably was). But he was just proving theorems and these are just mathematical truths. There was some big hullabaloo and his work was permitted to stay in the public domain. Weird times -- early Reagan years. I played bridge with Seligman back in 1988 at a math conference in Canada and as I recall everyone got really drunk.

Could someone please educate me. What is the practical use of finding the factors of these huge numbers?

Quote: Ace2

Could someone please educate me. What is the practical use of finding the factors of these huge numbers?

Decrypting RSA, for example. As in the "s" in your https among many others.

Quote: Ace2

Could someone please educate me. What is the practical use of finding the factors of these huge numbers?

Let's say we need to resolve something with the bet of a coin remotely and we DON'T have trust. Suppose we agree that I will flip a coin and you will call it. How do you trust me to report the flip correctly?

Here is a way.

I report to you that 57316309339135663435 is semi-prime, meaning the product of two primes.

Let x = the sum of the first three digits of both divisors.

If x = even, then I flipped heads
If x = odd, then I flipped tails.

After you call the flip, I'll provide the divisors to prove the outcome of the flip.

You may find a calculator online to cheat. I tried this one, but it seems my semi-prime number is too big for it.

p.s. This post aided by WizCalc and prime I.T..

My method for a remote coin flip is to pick the last digit of the next Dow Jones close. Used it many times.

Quote: Ace2

My method for a remote coin flip is to pick the last digit of the next Dow Jones close. Used it many times.

That's good, but what if we need to resolve a flip immediately?

If I understand your point, I think clarification is needed that no actual coin flip need take place.
The "flipper" has chosen either odd(tails) or even(heads) through the selection of the semi-prime, and the "caller" picks one. The semi-prime nature prevents the "flipper" from lying about his selection after learning of the "caller's" choice.

EDIT: Of course, the flipper could use an actual flip to determine even/odd, but the caller will have no way of knowing the selection method.

Quote: Wizard

That's good, but what if we need to resolve a flip immediately?

Not sure, never needed to. I just don't see too many people, outside of a forum like this, accepting or even understanding the large semi-prime method.

Quote: Ace2

Not sure, never needed to. I just don't see too many people, outside of a forum like this, accepting or even understanding the large semi-prime method.

I would argue they are depending on it when using encryption or making cryptocurrency transactions, even if they don't understand it.

Quote: Ace2

My method for a remote coin flip is to pick the last digit of the next Dow Jones close. Used it many times.

Have you checked whether that is historically a fair coin flip? I would have expected the Dow Jones to adhere to Benford’s law. Though for the last digit it might only be a minuscule bias.

Quote: Ace2

Not sure, never needed to. I just don't see too many people, outside of a forum like this, accepting or even understanding the large semi-prime method.

As other’s have said, the whole encryption industry is based on how impractical it is to find the prime factors of semi prime large numbers in a reasonable amount of time. Basis of public key / private key encryption.

Quote: unJon

Have you checked whether that is historically a fair coin flip? I would have expected the Dow Jones to adhere to Benford’s law. Though for the last digit it might only be a minuscule bias.

There was a time when organized crime used the last three digits of that day's NYSE volume as the three digits of its Numbers draw. There's a story where this backfired on them when somebody paid off someone at the NYSE to round the number to the nearest thousand before reporting it and then bet on 000.

Quote: Wizard

Let's say we need to resolve something with the bet of a coin remotely and we DON'T have trust. Suppose we agree that I will flip a coin and you will call it. How do you trust me to report the flip correctly?

Here is a way.

I report to you that 57316309339135663435 is semi-prime, meaning the product of two primes.

Er, 57316309339135663435 = 5 x 113 x 1,586,257 x 63,952,307,407

Quote: Wizard

I would argue they are depending on it when using encryption or making cryptocurrency transactions, even if they don't understand it.

I need to learn more about encryption then. I had no idea that prime factors were used for it

Quote: ThatDonGuy

Er, 57316309339135663435 = 5 x 113 x 1,586,257 x 63,952,307,407

Well, that is embarrassing. I do not know what went wrong there, but the fact my "semiprime number" ended in 5 should have been a clue it either wasn't or it would be easy to find the prime factors. Just pass the dunce cap -- I make no excuses.



Let me try again.

427768590362683222119329, I claim, is semi prime.

Heads = sum of all digits of prime factors even
Tails = sum of all digits of prime factors odd

Call it.

Quote: unJon

Have you checked whether that is historically a fair coin flip? I would have expected the Dow Jones to adhere to Benford’s law. Though for the last digit it might only be a minuscule bias.

Re Benfords Law, the leading digit is definitely biased. I'm betting the leading digit for tomorrow's close is going to be a 3. But I don't see how there could be any bias in the last digit (including cents)...maybe not even in the last four digits since 1%, a common daily movement, is about 340.00

Quote: unJon

Have you checked whether that is historically a fair coin flip? I would have expected the Dow Jones to adhere to Benford’s law.

Not everything, including the first digit of Chicago election results by precinct, should be expected to follow Benford's Law.

Quote: Wizard

Let me try again.

427768590362683222119329, I claim, is semi prime.

Heads = sum of all digits of prime factors even
Tails = sum of all digits of prime factors odd

Call it.

483936100541×883936102069

https://www.wolframalpha.com/input/?i=factors+of+427768590362683222119329

Here is an online calculator that will factorize numbers up to 70 digits in length.


Number Factorizer


And here is an online calculator that will tell you whether a number - up to 128 digits - is a prime number. You can also put in a number-up to 128 digits and it will give you the next highest prme number, or the immediately previous prime number.

Prime Numbers Generator and Checker

These are amazing calculator tools! I have been using them for at least a year.

Quote: miplet

483936100541×883936102069

https://www.wolframalpha.com/input/?i=factors+of+427768590362683222119329

Dang!

Hopefully I at least made my point about how primes can be used to verify a message is legitimate. I put in a number with about 100 digits and Wolfram said, "Standard computation time exceeded..." I am impressed Wolfram could factor what I challenged the board with so quickly, but it's my understanding if a semiprime number has hundreds of digits, it could take days to years of computer time to factor it.

Quote: ThatDonGuy

How did anyone possibly find either one of those in any reasonable length of time (other than "well, we found the other one first")?
And while I'm asking...what's the preferred method for primality testing (with 100% certainty) of non-Mersenne primes?

There are various methods for factorisation, (10^211-1) / 9 is obviously a special number, there may be an algorithm specifically for numbers of this type.
I don't know know your mathematical background, there are some algorithms which do not require heavy-duty mathematics, for example, Pollard rho, Pollard p-1, quadratic sieve.

As for primality testing, there is the AKS (Agrawal–Kayal–Saxena) primality test, which is guaranteed to work and is efficient in a precise technical sense.
What's used most often is the Rabin-Miller test, which is probabilistic, if a number fails the test, then it is definitely not prime, but some composite numbers may also pass the test. By using this test with various bases you can make the probability of a composite number passing the tests very small. People have proved theorems along the lines that if a 300 number digit passes the Rabin-Miller test with a certain set of bases, then the probability of it being composite is less than 10^(-50).
The Rabin-Miller test is very fast and easy to code.