Guest wrote: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 wrote: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 wrote: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 wrote: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 wrote: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 wrote: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 wrote: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.
Users browsing this forum: No registered users and 2 guests