Randomness can be a useful tool for solving problems.

Algebra

Randomness can be a useful tool for solving problems.

Postby Guest » Tue May 12, 2020 12:24 pm

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
Numbers.jpg
"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.

Postby Guest » Tue May 12, 2020 1:13 pm

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.

Postby Guest » Tue May 12, 2020 1:31 pm

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.

Postby Guest » Tue May 12, 2020 1:52 pm

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

Reference Link:

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

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

Postby Guest » Tue May 12, 2020 2:15 pm

The algebra behind integer multiplication is quite rich and interesting.

Relevant Reference Link:

'Multiplication Algorithm',

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

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

Postby Guest » Tue May 12, 2020 2:36 pm

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?


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
 

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

Postby Guest » Tue May 12, 2020 5:40 pm

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
 

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

Postby Guest » Thu May 14, 2020 2:57 pm

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.

Postby Guest » Thu May 14, 2020 10:06 pm

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

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

Postby Guest » Fri May 22, 2020 10:43 am

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.

Postby Guest » Fri May 22, 2020 9:04 pm

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

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

Postby Guest » Fri May 22, 2020 9:34 pm

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
 

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

Postby Guest » Fri May 22, 2020 9:47 pm

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.


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.

Postby Guest » Sun May 24, 2020 1:54 am

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
Attachments
1000-Digit Integer is a product of two unknow primes, each with 500 digits..gif
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.

Postby Guest » Sun May 24, 2020 2:19 am

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 ?
Attachments
Good Luck!.jpg
Good Luck!.jpg (10.69 KiB) Viewed 288 times
Guest
 

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

Postby Guest » Sun May 24, 2020 1:52 pm

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 ?


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
I is a 1000-Digit Integer that is a product of two unknown primes, p and q, each with 500 digits..gif
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
Silhouette of Sherlock Holmes.jpg
"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.

Postby Guest » Sun May 24, 2020 5:37 pm

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
 

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

Postby Guest » Sun May 24, 2020 6:19 pm

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

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

Postby Guest » Sun May 24, 2020 6:20 pm

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.

Postby Guest » Mon May 25, 2020 7:38 pm

"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

Return to Algebra



Who is online

Users browsing this forum: Google [Bot] and 1 guest