Randomness can be a useful tool for solving problems.

Algebra

Randomness can be a useful tool for solving problems.

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/.
Attachments
"Randomness is an underappreciated mathematical tool." -- Prof. Kevin Hartnett.
Numbers.jpg (367.57 KiB) Viewed 392 times
Guest

Re: Randomness can be a useful tool for solving problems.

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

Re: Randomness can be a useful tool for solving problems.

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?

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

Re: Randomness can be a useful tool for solving problems.

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

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

Re: Randomness can be a useful tool for solving problems.

The algebra behind integer multiplication is quite rich and interesting.

'Multiplication Algorithm',

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

Re: Randomness can be a useful tool for solving problems.

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?

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

Re: Randomness can be a useful tool for solving problems.

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.

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

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

Re: Randomness can be a useful tool for solving problems.

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

Re: Randomness can be a useful tool for solving problems.

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)

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

and we let $$q = \sum_{m=0}^{499 }q_{m }*10^{m}$$.

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

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

...
Guest

Re: Randomness can be a useful tool for solving problems.

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

Re: Randomness can be a useful tool for solving problems.

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!

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 $$q < \sqrt{I} < p$$. We should consider how close q is to q. And compute roughly how many prime candidates there are for p and q...
Guest

Re: Randomness can be a useful tool for solving problems.

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

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

Re: Randomness can be a useful tool for solving problems.

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

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

Re: Randomness can be a useful tool for solving problems.

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 $$\sqrt{I}$$ ?

What are p and q?

Attachments
What are the two prime factors of the 1000-digit integer?
1000-Digit Integer is a product of two unknow primes, each with 500 digits..gif (32.25 KiB) Viewed 288 times
Guest

Re: Randomness can be a useful tool for solving problems.

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

Does q | I ?
Attachments
Good Luck!.jpg (10.69 KiB) Viewed 288 times
Guest

Re: Randomness can be a useful tool for solving problems.

Guest wrote:Since $$I = p * q$$, we can randomly select a prime (a 500-digit integer), q, relatively close to $$\sqrt{I}$$.

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.
Attachments
What are the prime factors, p and q, for I?
I is a 1000-Digit Integer that is a product of two unknown primes, p and q, each with 500 digits..gif (32.25 KiB) Viewed 281 times
"The conviction of the solvability of every mathematical problem is a powerful incentive to the worker. We hear within us the perpetual call: There is the problem. Seek its solution. You can find it by pure reason, for in mathematics there is no ignorabimus." -- David Hilbert.
Silhouette of Sherlock Holmes.jpg (5.13 KiB) Viewed 281 times
Guest

Re: Randomness can be a useful tool for solving problems.

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

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.

'Polynomial Time',

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

Re: Randomness can be a useful tool for solving problems.

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.
Attachments
Please keep an open mind..jpg (11.67 KiB) Viewed 266 times
Guest

Re: Randomness can be a useful tool for solving problems.

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

Re: Randomness can be a useful tool for solving problems.

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

Next