Randomness can be a useful tool for solving problems.

Algebra

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

Postby Guest » Tue Jun 09, 2020 2:46 pm

An Update: ([tex]\sqrt{I}[/tex])

The Minimum Square Greater Than I = p * q: :idea:

Generally, our integer factorization problem, I = p * q, is an integer optimization problem. :idea:

We seek to find the minimum positive integer, [tex]1 \le\lambda < \sqrt{I}[/tex], such that

[tex]\sqrt{I + \lambda^{2}}[/tex] is a positive integer. :idea:

Remark: [tex]p - q = 2\lambda[/tex] where p and q are unknown odd primes such that p > q and such that I = p * q where I is known.

Dave.
Guest
 

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

Postby Guest » Tue Jun 09, 2020 5:29 pm

Dave wrote:An Update: ([tex]\sqrt{I}[/tex])

The Minimum Square Greater Than I = p * q: :idea:

Generally, our integer factorization problem, I = p * q, is an integer optimization problem. :idea:

We seek the minimum positive integer, [tex]1 \le\lambda < \sqrt{I}[/tex], such that

[tex]\sqrt{I + \lambda^{2}}[/tex] is a positive integer. :idea:

Remark: [tex]p - q = 2\lambda[/tex] where p and q are unknown odd primes such that p > q and such that I = p * q where I is known.

Dave.


Does fast convergence (polynomial time) from [tex]\sqrt{I}[/tex], exclusively, to [tex]\lambda[/tex] exists? Why? How?

Does fast convergence (polynomial time) from 1, inclusively, to [tex]\lambda[/tex] exists? Why? How?
Attachments
Figure-D1-Polynomial-time-complexity-classes.png
Figure-D1-Polynomial-time-complexity-classes.png (15.35 KiB) Viewed 88 times
Guest
 

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

Postby Guest » Tue Jun 09, 2020 7:02 pm

Remarks: [tex]\lambda[/tex] exists and is unique since the prime factor, q, exists and is unique.

Moreover, [tex]3 \le q < \sqrt{I} = \sqrt{p * q} < p[/tex].
Guest
 

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

Postby Guest » Thu Jun 11, 2020 6:41 am

An Update: ( [tex]\sqrt{I} / 2[/tex] )

The Minimum Square Greater Than I = p * q: :idea:

Generally, our integer factorization problem, I = p * q, is an integer optimization problem. :idea:

We seek the minimum positive integer, [tex]1 \le\lambda < \sqrt{I} / 2[/tex], such that

[tex]\sqrt{I + \lambda^{2}}[/tex] is a positive integer. :idea:

Remark: [tex]p - q = 2\lambda[/tex] where p and q are unknown odd primes such that p > q and such that I = p * q where I is known.

Dave.

Does fast convergence (polynomial time) from [tex]\sqrt{I} / 2[/tex], exclusively, to [tex]\lambda[/tex] exists? Why? How?

Does fast convergence (polynomial time) from 1, inclusively, to [tex]\lambda[/tex] exists? Why? How?
Guest
 

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

Postby Guest » Thu Jun 11, 2020 6:44 am

Guest wrote:An Update: ( [tex]\sqrt{I} / 2[/tex] )

The Minimum Square Greater Than I = p * q: :idea:

Generally, our integer factorization problem, I = p * q, is an integer optimization problem. :idea:

We seek the unique positive integer, [tex]1 \le\lambda < \sqrt{I} / 2[/tex], such that

[tex]\sqrt{I + \lambda^{2}}[/tex] is a positive integer. :idea:

Remark: [tex]p - q = 2\lambda[/tex] where p and q are unknown odd primes such that p > q and such that I = p * q where I is known.

Dave.

Does fast convergence (polynomial time) from [tex]\sqrt{I} / 2[/tex], exclusively, to [tex]\lambda[/tex] exists? Why? How?

Does fast convergence (polynomial time) from 1, inclusively, to [tex]\lambda[/tex] exists? Why? How?
Guest
 

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

Postby Guest » Thu Jun 11, 2020 6:58 am

An Update for [tex]I = p * q = 8.671... * 10^{999}[/tex]:

Guest wrote:Now suppose we have access to a worldwide network of one billion personal computers for solving our integer factorization problem.

We program computer one to search randomly for a solution in the range:

[tex]1 \le \lambda\ < 3.09 * 10^{489}[/tex];

We program computer two to search randomly for a solution in the range:

[tex]3.09 * 10^{489} \le \lambda < 2 * 3.09 * 10^{489}[/tex];

We program computer three to search randomly for a solution in the range:

[tex]2 * 3.09 * 10^{489} \le \delta < 3 * 3.09 * 10^{489}[/tex];
...
...
...

We program the billionth computer to search randomly for a solution in the range:

[tex](10^{9} - 1) * 3.09 * 10^{489} \le \lambda < 3.09 * 10^{498}[/tex].

We
Guest
 

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

Postby Guest » Thu Jun 11, 2020 7:12 am

Guest wrote:An Update for [tex]I = p * q = 8.671... * 10^{999}[/tex]:

Guest wrote:Now suppose we have access to a worldwide network of one billion personal computers for solving our integer factorization problem.

We program computer one to search randomly for a solution in the range:

[tex]1 \le \lambda\ < 3.09 * 10^{489}[/tex];

We program computer two to search randomly for a solution in the range:

[tex]3.09 * 10^{489} \le \lambda < 2 * 3.09 * 10^{489}[/tex];

We program computer three to search randomly for a solution in the range:

[tex]2 * 3.09 * 10^{489} \le \lambda < 3 * 3.09 * 10^{489}[/tex];
...
...
...

We program the billionth computer to search randomly for a solution in the range:

[tex](10^{9} - 1) * 3.09 * 10^{489} \le \lambda < 3.09 * 10^{498}[/tex].
Guest
 

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

Postby Guest » Thu Jun 11, 2020 10:41 am

Guest wrote:
Guest wrote:An Update: ( [tex]\sqrt{I} / 2[/tex] )

The Appropriate Square Greater Than I = p * q: :idea:

Generally, our integer factorization problem, I = p * q, is an integer optimization problem. :idea:

We seek the unique positive integer, [tex]1 \le\lambda < \sqrt{I} / 2[/tex], such that

[tex]\sqrt{I + \lambda^{2}}[/tex] is a positive integer. :idea:

Remark: [tex]p - q = 2\lambda[/tex] where p and q are unknown odd primes such that p > q and such that I = p * q where I is known.

Dave.

Does fast convergence (polynomial time) from [tex]\sqrt{I} / 2[/tex], exclusively, to [tex]\lambda[/tex] exists? Why? How?

Does fast convergence (polynomial time) from 1, inclusively, to [tex]\lambda[/tex] exists? Why? How?


Let's ponder the following sum of two functions, [tex]n(\lambda)[/tex] and [tex]∆n(\lambda)[/tex]:

[tex]n(\lambda) + ∆n(\lambda) = \sqrt{I + \lambda^{2}}[/tex] for some positive integers, [tex]n(\lambda)[/tex] and [tex]\lambda[/tex], where [tex]0 \le ∆n(\lambda) < 1[/tex].

Remark: [tex]1 \le \lambda < \frac{\sqrt{I}}{2}[/tex] and I = p * q where I is known.

Key Ideas: Power Series Expansion, Convergence, Rate of Convergence, etc.

Relevant Reference Link:

'Power series',

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

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

Postby Guest » Thu Jun 11, 2020 11:18 am

Let's ponder the following sum of two functions, [tex]n(\lambda)[/tex] and [tex]∆n(\lambda)[/tex]:

[tex]n(\lambda) + ∆n(\lambda) = \sqrt{I + \lambda^{2}}[/tex] for some positive integers, [tex]n(\lambda)[/tex] and [tex]\lambda[/tex], where [tex]0 \le ∆n(\lambda) < 1[/tex].

Remark: [tex]1 \le \lambda < \frac{\sqrt{I}}{2}[/tex] and I = p * q where I is known.

Key Ideas: Power Series Expansion, Convergence, Rate of Convergence, etc.

Relevant Reference Link:

'Power series',

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


Can we explicitly identify [tex]n(\lambda)[/tex] in the expression,[tex]\sqrt{I + \lambda^{2}}[/tex] ?

And can we explicitly identify [tex]∆n(\lambda)[/tex] in the expression, [tex]\sqrt{I + \lambda^{2}}[/tex] ?
Guest
 

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

Postby Guest » Thu Jun 11, 2020 12:52 pm

Guest wrote:
Let's ponder the following sum of two functions, [tex]n(\lambda)[/tex] and [tex]∆n(\lambda)[/tex]:

[tex]n(\lambda) + ∆n(\lambda) = \sqrt{I + \lambda^{2}}[/tex] for some positive integers, [tex]n(\lambda)[/tex] and [tex]\lambda[/tex], where [tex]0 \le ∆n(\lambda) < 1[/tex].

Remark: [tex]1 \le \lambda < \frac{\sqrt{I}}{2}[/tex] and I = p * q where I is known.

Key Ideas: Power Series Expansion, Convergence, Rate of Convergence, etc.

Relevant Reference Link:

'Power series',

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


Can we explicitly identify [tex]n(\lambda)[/tex] in the expression,[tex]\sqrt{I + \lambda^{2}}[/tex] ?

And can we explicitly identify [tex]∆n(\lambda)[/tex] in the expression, [tex]\sqrt{I + \lambda^{2}}[/tex] ?


Remark: The power series expansion of [tex]\sqrt{I + \lambda^{2}}[/tex] may or may not help us here.
Guest
 


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

Postby Guest » Thu Jun 11, 2020 1:22 pm

Remark: We are seeking either a proof/algorithm or a disproof that our integer factorization problem can be solved in polynomial time.
Guest
 

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

Postby Guest » Sun Jun 14, 2020 2:07 am

Guest wrote:Remark: We are seeking either a proof/algorithm or a disproof that our integer factorization problem can be solved in polynomial time.


Relevant Reference Links:

'Integer factorization',

https://en.wikipedia.org/wiki/Integer_factorization#:~:text=Unsolved%20problem%20in%20computer%20science%3A&text=In%20number%20theory%2C%20integer%20factorization,process%20is%20called%20prime%20factorization.&text=Not%20all%20numbers%20of%20a%20given%20length%20are%20equally%20hard%20to%20factor.;

'Why isn't integer factorization in complexity P, when you can factorize n in O(√n) steps?',

https://math.stackexchange.com/questions/1624390/why-isnt-integer-factorization-in-complexity-p-when-you-can-factorize-n-in-o%E2%88%9A.
Attachments
Integer Factorization.jpg
Integer Factorization.jpg (67.57 KiB) Viewed 59 times
Guest
 

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

Postby Guest » Sun Jun 14, 2020 4:27 am



The general continued fraction of [tex]\sqrt{I + \lambda^{2}}[/tex] offers great promise. So between the power series expansion of [tex]\sqrt{I + \lambda^{2}}[/tex] and its general continued fraction represention, we hope to solve [tex]\triangle n(\lambda) = 0[/tex]...

Good Luck! :)
Guest
 

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

Postby Guest » Sun Jun 14, 2020 11:46 am

Guest wrote:


The general continued fraction of [tex]\sqrt{I + \lambda^{2}}[/tex] offers great promise. So between the power series expansion of [tex]\sqrt{I + \lambda^{2}}[/tex] and its general continued fraction representation, we hope to solve [tex]\triangle n(\lambda) = 0[/tex]...

Good Luck! :)
Guest
 

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

Postby Guest » Mon Jun 15, 2020 1:22 am

What is the nearest perfect square to I = p * q such p and q are primes?[/b]

Generally, that question is difficult to answer. Here are some simple examples:

If I = 91, then 100 is the nearest perfect square such that p and q are primes ([tex]10 \pm \lambda[/tex]), and therefore, [tex]\lambda = 3[/tex].

If I = 32,639, then 36,864 is the nearest perfect square such that p and q are primes ([tex]192 \pm \lambda[/tex]), and therefore, [tex]\lambda = 65[/tex].
Guest
 

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

Postby Guest » Mon Jun 15, 2020 12:33 pm

Dave wrote:FYI: 'Continued fraction',

https://en.wikipedia.org/wiki/Continued_fraction#Infinite_continued_fractions_and_convergents.

The generalized continued fraction of [tex]\sqrt{I + \lambda^{2}}[/tex] offers great promise. So between the power series expansion of [tex]\sqrt{I + \lambda^{2}}[/tex] and its generalized continued fraction representation, we hope to solve [tex]\triangle n(\lambda) = 0[/tex]...

Good Luck! :)


A Tentative Update: [tex]\beta(I) * (\frac{1 + \sqrt{ \frac{(\sqrt{2} - 1) * I}{2}}}{2}) \le \lambda < \sqrt{ \frac{(\sqrt{2} - 1) * I}{2}}[/tex] where [tex]0 < \beta(I) \le 1[/tex].

Remark: We want to construct a convergent sequence to solve [tex]\lambda[/tex].
Guest
 

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

Postby Guest » Mon Jun 15, 2020 12:47 pm

\ge
Guest wrote:
Dave wrote:FYI: 'Continued fraction',

https://en.wikipedia.org/wiki/Continued_fraction#Infinite_continued_fractions_and_convergents.

The generalized continued fraction of [tex]\sqrt{I + \lambda^{2}}[/tex] offers great promise. So between the power series expansion of [tex]\sqrt{I + \lambda^{2}}[/tex] and its generalized continued fraction representation, we hope to solve [tex]\triangle n(\lambda) = 0[/tex]...

Good Luck! :)


A Tentative Update: [tex]\beta(I) * (\frac{1 + \sqrt{ \frac{(\sqrt{2} - 1) * I}{2}}}{2}) \le \lambda < \sqrt{ \frac{(\sqrt{2} - 1) * I}{2}}[/tex] where [tex]0 < \beta(I) \le 1[/tex].

Remark: We want to construct a convergent sequence to solve [tex]\lambda[/tex].


Case 1: [tex]\lambda > \frac{1 + \sqrt{ \frac{(\sqrt{2} - 1) * I}{2}}}{2}[/tex] when [tex]\beta(I) = 1[/tex].

Case 2: [tex]\lambda = \beta(I) * (\frac{1 + \sqrt{ \frac{(\sqrt{2} - 1) * I}{2}}}{2})[/tex] when [tex]0 < \beta(I) \le 1[/tex].
Guest
 

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

Postby Guest » Mon Jun 15, 2020 1:11 pm

Guest wrote:\ge
Guest wrote:
Dave wrote:FYI: 'Continued fraction',

https://en.wikipedia.org/wiki/Continued_fraction#Infinite_continued_fractions_and_convergents.

The generalized continued fraction of [tex]\sqrt{I + \lambda^{2}}[/tex] offers great promise. So between the power series expansion of [tex]\sqrt{I + \lambda^{2}}[/tex] and its generalized continued fraction representation, we hope to solve [tex]\triangle n(\lambda) = 0[/tex]...

Good Luck! :)


A Tentative Update: [tex]\beta(I) * (\frac{1 + \sqrt{ \frac{(\sqrt{2} - 1) * I}{2}}}{2}) \le \lambda < \sqrt{ \frac{(\sqrt{2} - 1) * I}{2}}[/tex] where [tex]0 < \beta(I) \le 1[/tex].

Remark: We want to construct a convergent sequence that solves [tex]\lambda[/tex].


Depending on I, only one of the following two cases is true!

Case 1: [tex]\lambda > \frac{1 + \sqrt{ \frac{(\sqrt{2} - 1) * I}{2}}}{2}[/tex] when [tex]\beta(I) = 1[/tex].

Case 2: [tex]\lambda = \beta(I) * (\frac{1 + \sqrt{ \frac{(\sqrt{2} - 1) * I}{2}}}{2})[/tex] when [tex]0 < \beta(I) \le 1[/tex].
Guest
 

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

Postby Guest » Mon Jun 15, 2020 1:40 pm

Remarks: Both cases, one and two, are equally challenging. And each case requires further subintervals or subsequences... We hope that further developments will achieve a solution.
Guest
 

PreviousNext

Return to Algebra



Who is online

Users browsing this forum: No registered users and 2 guests