Randomness can be a useful tool for solving problems.

[Guest]

FYI: 'How Randomness Can Make Math Easier:
Randomness would seem to make a mathematical statement harder to prove. In fact, it often does the opposite.'

https://www.quantamagazine.org/how-randomness-can-make-math-easier-20190709/.

[Guest]

How can we use the idea of randomness with some simple rules of arithmetic to discover the two prime factors of 182,211,377,207?

[Guest]

How can we use the idea of randomness with some simple rules of arithmetic to discover the two prime factors of 182,211,377,207?

Choice A:

? ? ? ? ? 1

x

? ? ? ? ? 7
_________

or

Choice B:

? ? ? ? ? 3

x

? ? ? ? ? 9
_________

What is the right choice, A or B?

And what are the answers (the right digits, 0 - 9) to the questions (?)

[Guest]

One of the simple rules for integer multiplication is casting out nines.

Reference Link:

https://en.wikipedia.org/wiki/Casting_out_nines#Multiplication.

[Guest]

The algebra behind integer multiplication is quite rich and interesting.

Relevant Reference Link:

'Multiplication Algorithm',

https://en.wikipedia.org/wiki/Multiplication_algorithm.

[Guest]

How can we use the idea of randomness with some simple rules of arithmetic to discover the two prime factors of 182,211,377,207?

Source Link:

https://www.wolframalpha.com/input/?i=Prime%28RandomInteger%5B%7B5000%2C+100000%7D%5D%29*+Prime%28RandomInteger%5B%7B1000%2C+100000%7D%5D%29.

[Guest]

Hmm. It seems a construction of a neural network will be beneficial here. It could greatly aid our efforts to solve our integer factorization problem and much more difficult ones too.

Relevant Reference Link:

'Integer Factorization with a Neuromorphic Sieve', by Profs. John V. Monaco and Manuel M. Vindiola,

https://arxiv.org/pdf/1703.03768.pdf

[Guest]

Hmm. Let's imagine we have a depth algorithm that solves the problem of finding the two unknown large prime factors of a known integer.

How does it work?

Suppose we want to factor a known 1000-digit integer, I, that we know is a product of two unknown large primes, p and q, each has 500 digits.

Hmm... (thinking)

[Guest]

Hmm. Let's imagine we have a depth algorithm that solves the problem of finding the two unknown large prime factors of a known integer.

How does it work?

Suppose we want to factor a known 1000-digit integer, I, that we know is a product of two unknown large primes, p and q, each has 500 digits.

Hmm... (thinking)

Since [tex]I = \sum_{k=0}^{999 }i_{k }*10^{k}[/tex], we assume [tex]p > q[/tex], we let [tex]p = \sum_{j=0}^{499 }p_{j }*10^{j}[/tex],

and we let [tex]q = \sum_{m=0}^{499 }q_{m }*10^{m}[/tex].

We know that [tex]i_{0 } \in[/tex] {1, 3, 7, 9}, and we compute [tex]p_{0 }[/tex] and [tex]q_{0 }[/tex] accordingly.

There's a 33% to 50% chance that our choice for [tex]p_{0 }[/tex] and [tex]q_{0 }[/tex] is correct. Right? Why?

...

[Guest]

Suppose we are certain that we have computed correctly some digits of p and q based on I.

How reliable are our computations?

Remark: That is a difficult question!

[Guest]

Suppose we are certain that we have computed correctly some digits of p and q based on I.

How reliable are our computations?

Remark: That is a difficult question!

Your question is not a difficult question. The answer is fairly simple.

Only a complete solution (p and q) is acceptable. Having a few digits of p or q is not enough! And we cannot know if they are correct until we know p and q.

And we are certain that [tex]q < \sqrt{I} < p[/tex]. We should consider how close q is to q. And compute roughly how many prime candidates there are for p and q...

[Guest]

FYI: There are roughly [tex]7.8 * 10^{496}[/tex] prime candidates for q according to the Prime Number Theorem. And if we know q, then we can compute [tex]p = \frac{I}{q}[/tex].

Relevant Reference Link:

https://www.wolframalpha.com/input/?i=%289.99+*10%5E999%29%5E.5%2Flog%28%289.99+*10%5E1000%29%5E.5%29+-+9.99*10%5E498%2Flog%289.99*10%5E498%29.

[Guest]

FYI: There are roughly [tex]7.8 * 10^{496}[/tex] prime candidates for q according to the Prime Number Theorem. And if we know q, then we can compute [tex]p = \frac{I}{q}[/tex].

Relevant Reference Link:

https://www.wolframalpha.com/input/?i=%289.99+*10%5E999%29%5E.5%2Flog%28%289.99+*10%5E1000%29%5E.5%29+-+9.99*10%5E498%2Flog%289.99*10%5E498%29.

Moreover, unless we are extremely lucky, randomness (i.e. randomly generating all digits of p) alone will not solve our problem.

[Guest]

We are given the integer, I (a 1000-digit integer: please see attachment below), which is a product two unknown primes, p (a 500-digit integer) and q (a 500-digit integer).

What is [tex]\sqrt{I}[/tex] ?

What are p and q?

Source Link:

https://www.wolframalpha.com/input/?i=NextPrimeNumber%5BRandomReal%5B%7B1%2C10%7D%5D+*10%5E499%5D+*+NextPrimeNumber%5BRandomReal%5B%7B1%2C10%7D%5D+*10%5E499%5D

[Guest]

Since [tex]I = p * q[/tex], we can randomly select a prime (a 500-digit integer), q, relatively close to [tex]\sqrt{I}[/tex].

Does q | I ?

[Guest]

Since [tex]I = p * q[/tex], we can randomly select a prime (a 500-digit integer), q, relatively close to [tex]\sqrt{I}[/tex].

Does q | I ?

Let's assumed we have not discovered the prime factors, p and q, for I. What can we do to aid our solution search?

Since the last digit of I (please see attachment below) is 9, we expect the last digits of p and q, to belong to
one of the sets, {1, 9}, {3, 3}, or {7, 7}.


And since the first digit of I is 8, we expect the first digits of p and q, to belong to one of the sets,
{1, 8}, {1, 6}, {1, 5},..., {2, 3}, {2,4}.

Because of potential carry digits as the result of p * q, we are more challenged to find the first digits of p and q.

Thus far, randomly generating most digits of p and q is still our main tool for solving our problem.

However, we hope to develop a learning algorithm that will greatly aid our random solution search.

[Guest]

If we consider the first four digits, 8671, of I, then we compute [tex]\sqrt{8671} \approx 93[/tex].

Therefore, we guess 89 is the first two digits of q, and that 97 is the first two digits of p.

And if we consider the last four digits, 5999 = 857 * 7, of I, then we guess 857 and 007 are the last three digits of either, p or q.

Remark: Our initial guesses could be wrong! But we need to start somewhere, and we hope our ongoing random search converges to a true solution in polynomial time.

Relevant Reference Link:

'Polynomial Time',

https://mathworld.wolfram.com/PolynomialTime.html.

[Guest]

How do we manage to solve our problem in polynomial time?

It may require a sophisticated learning algorithm involving a neural network and some other tools. We just beginning, and more resources/rules/results will come.

[Guest]

How do we manage to solve our problem in polynomial time?

It may require a sophisticated learning algorithm involving a neural network and some other tools. We're just beginning, and more resources/rules/results will come.

[Guest]

"Simple seeks simplest (best) solution."

Remark: Complex integer factorization is complex arithmetic. And the more we know about complex arithmetic, the less we need randomness/guessing to help us solve our current problem.

And we should also consider the relevant facts/information about our problem...