Jump to content

Simple yet interesting.


Trurl
 Share

Recommended Posts

19 hours ago, Trurl said:

I have much more to share.

I am looking forward to a connection to RSA encryption and prime factorisation of large integers. 

On 6/20/2021 at 10:50 PM, Trurl said:

Plug and chug

Ok.

I'll try two examples: 8633, 8637. Both are semi primes. 

NSolve  [( x^4/((8637)^2 + x)) == 1]
x≈-92.935
x≈92.935

NSolve  [( x^4/((8633)^2 + x)) == 1]
x≈-92.914
x≈92.914

@Trurl Is this helpful for someone looking for the prime factors of the numbers 8633 and 8637? If so, how?

 

Edited by Ghideon
grammar
Link to comment
Share on other sites

Ok.

I'll try two examples: 8633, 8637. Both are semi primes. 

NSolve  [( x^4/((8637)^2 + x)) == 1]

x≈-92.935

x≈92.935

 

NSolve  [( x^4/((8633)^2 + x)) == 1]

x≈-92.914

x≈92.914

@Trurl Is this helpful for someone looking for the prime factors of the numbers 8633 and 8637? If so, how?

 

 

Yes the numbers are too close to estimate. But I still have faith in the Pappy Craylar method. After all 3 < 92 and 3^4/(8637^2+3)=0.000001732

Which Is close to zero where the error is supposed to be near anyway.

 

Remember when I said we needed to test the logarithmic curve of 3*5; 3*7; 3*11 and so forth to find the error change as 3*Prime number increases?

 

I know your smart and are looking for holes in the PC method. That is what you are supposed to do. But I know you are smart enough to understand it.

 

A fix to to great number of possible estimates is to isolate y as x is isolated. Then we will see a better picture of what is happening when SemiPrimes are factored.

Link to comment
Share on other sites

20 hours ago, Trurl said:

Yes the numbers are too close to estimate. But I still have faith in the Pappy Craylar method. After all 3 < 92 and 3^4/(8637^2+3)=0.000001732

Which Is close to zero where the error is supposed to be near anyway.

How did you get the number 3? From your formulas or by some other method? 

20 hours ago, Trurl said:

I know your smart and are looking for holes in the PC method. That is what you are supposed to do. But I know you are smart enough to understand it.

I do not understand. If that is due to my lack of abilities or lack of valid explanations, I'll let others judge. 

And I am still waiting for a connection to RSA encryption and prime factorisation of large integers. 

Link to comment
Share on other sites

(y^3 * pnp^3 - y^2 * pnp + pnp) / (y^3 * pnp + y^2) = pnp^2

y is now isolated as x was. Ready to simplify.

No, you uncovered a weakness of the PC method. That is that the error varies between 0 and 1. The first SemiPrime was close to 94. I factored the second to be sure. But by working with the equation for years that it could be a smaller Prime factor.

 

The trouble is without knowing the true error testing numbers less than 94 in the example, narrows the selection but not more useful than division. We need exact results and not an estimate. But does that exist?

 

3 possible solutions:

 

  • Isolate y and compare to x
  • Investigate the curve of the graph of the equation between 0 and 1
  • Find a pattern in the error. An error not spanning such a large range.

 

 

 

3^4/(8637^2+3)=0.000001732

 

3 < 94 but the number of importance is 0.00001732. It causes 3 to be hidden when starting at 1 and not zero.

 

Questions are good. It is quite possible I am wrong. But I see something or I wouldn’t have put so much effort.

 

From Wikipedia:

 

Semiprimes are highly useful in the area of cryptography and number theory, most notably in public key cryptography, where they are used by RSA and pseudorandom number generators such as Blum Blum Shub. These methods rely on the fact that finding two large primes and multiplying them together (resulting in a semiprime) is computationally simple, whereas finding the original factors appears to be difficult. In the RSA Factoring Challenge, RSA Security offered prizes for the factoring of specific large semiprimes and several prizes were awarded. The original RSA Factoring Challenge was issued in 1991, and was replaced in 2001 by the New RSA Factoring Challenge, which was later withdrawn in 2007.[7]

 

https://en.m.wikipedia.org/wiki/Semiprime

Link to comment
Share on other sites

I'm coming to this thread late and trying to make sense of it. @Trurl, your writing style is difficult to parse. You should also learn [math]\LaTeX[/math] which will make it easier for others to read your math.

 

@Trurl correct me if I'm wrong about your work and motivation. This is what I understand you're trying to do. The motivation is to find a method of approximating the smaller prime factor of a semi-prime. So, if [math]N[/math] is a semi-prime and [math]p[/math] and [math]q[/math] are primes such that [math]q<p[/math] and [math]N=pq[/math], then you want a function [math]f(x)[/math] such that there exists a point [math](n, f(n))[/math] where [math]f(n) \approx q[/math].

And the reason you want such a function is so if [math]n[/math] is known or easy to find, then you limit the search space to find [math]q[/math] and you also approximately know the lower bound for [math]p[/math] because it must be greater than [math]q[/math].

 

7 hours ago, Ghideon said:

How did you get the number 3? From your formulas or by some other method? 

I do not understand. If that is due to my lack of abilities or lack of valid explanations, I'll let others judge. 

And I am still waiting for a connection to RSA encryption and prime factorisation of large integers. 

I don't think he gets the number 3, it's a counter example.

Edited by FragmentedCurve
Link to comment
Share on other sites

\frac {\text {pnp}^3 y^3 - \text {pnp} y^2 + \text {pnp}} {\text {pnp} y^3 + y^2}

 

Quote

correct me if I'm wrong about your work and motivation. This is what I understand you're trying to do. The motivation is to find a method of approximating the smaller prime factor of a semi-prime. So, if N is a semi-prime and p and q are primes such that q<p and N=pq, then you want a function f(x) such that there exists a point (n,f(n)) where f(n)q.

And the reason you want such a function is so if n is known or easy to find, then you limit the search space to find q and you also approximately know the lower bound for p because it must be greater than q.

Yes that is exactly it. But does it work? I think it works, but does it prove useful?

I call "N": pnp and "p and q": "x and y"

Given N (I call pnp) we estimate x. And in the latest post I am trying to find y, the larger factor.

 

\frac {\text {pnp}^3 y^3 - \text {pnp} y^2 + \text {pnp}} {\text {pnp} y^3 + y^2}

\frac {\text {pnp}^3 y^3 - \text {pnp} y^2 + \text {pnp}} {\text {pnp} y^3 + y^2}

 

\[\frac {\text {pnp}^3 y^3 - \text {pnp} y^2 + \t
      ext {pnp}} {\text {pnp} y^3 + y^2}\]

Link to comment
Share on other sites

The new "y isolated" equation does not work. It was based on the "x isolated" equation, but does not work.

Does anyone see a way to isolate y knowing only pnp?

Link to comment
Share on other sites

I don't really know how to answer your questions because they don't really make sense. From what I can gather, the important thing is you want [math]x>q[/math]. Below I give your conjecture with a simpler function that has the same property along with a proof. 

Conjecture

Given the function [math]f(x)=\frac{x^2}{N}[/math], if N=pq  is a semiprime and p>q , then p>x>q when f(x)=1 .

Proof

[math]1=\frac{x^2}{N} \implies \sqrt{N}=x[/math]

Given that p>q , then [math]p^2>N>q^2 \implies p>\sqrt{N}>q \therefore p>x>q[/math].

Edited by FragmentedCurve
LaTeX issues
Link to comment
Share on other sites

Here are my equations to review. There are quite possibly hundreds of variations. This is what I meant by isolating x and y in the equations. I mean isolated p and q separately, knowing only N. There are 3 equations. I am just getting used to Latex so I hope this is readable. If necessary I will post corrections. But it is these 3 separate equations I want you to test.

 

 

p^3 - (p^3*N^2) / (N^2 + p)

\[p^3 - \frac {N^2 p^3} {N^2 + p}\]


___ ___ ___ ___ ___ ___ ___ ___ ___ ___ ___ ___ ___ ___ ___ ___ ___ _

The above equation should be close to zero, but sometimes the error is closer to 1

 

 

 


(p^3 *N) / (N^2 + p) = fraction
fraction/ q = fraction / (N /p)
Sqrt[fraction / (N /p)] * N = p^2


\[\frac{N p^3}{N^2+p}=\text{fraction}\]
___________________________________________________________________

The above equations are the second example.

 

 

 

 

q = Sqrt[(N*q^2 + q)/ N]

q^2 - (N*q^2 + q)/ N  is approximately 0

In the case where N = 85 and q = 17,
        q^2 - (N*q^2 + q)/ N  is 1/x or 1/5 or 0.2
        0.2 * 85 = x or 5 in this example

 

\[q^2 - \frac {0\text {approximately}\t
      ext {is}\left (N q^2 + q \right)} {N}\]

Final equations are a proposed method for finding q, knowing only N

 

 

I have been working with the first equation for awhile. The other 2 are based on the first, but still need tried.

There is nothing fancy here. I am just comparing how numbers divide.

Link to comment
Share on other sites

 Note: These are 3 separate groups of equations. They are separated by lines.

 

 

 

\[p^3 - \frac {N^2 p^3} {N^2 + p}\]


___ ___ ___ ___ ___ ___ ___ ___ ___ ___ ___ ___ ___ ___ ___ ___ ___ _

The above equation should be close to zero, but sometimes the error is closer to 1

 

 

 

\[\frac{N p^3}{N^2+p}=\text{fraction}\]

because q = N/p

\[\frac{\text{fraction}}{q}=\frac{\text{fraction}}{\frac{N}{p}}\]

\[N \sqrt{\frac{\text{fraction}}{\frac{N}{p}}}=p^2\]
___________________________________________________________________

The above equations are the second example.

 

 

\[q = \sqrt {\frac {N q^2 + q} {N}}\]

square q

\[q^2-\frac{ \left(N q^2+q\right)}{N}\]

In the case where N = 85 and q = 17,

        \[q^2 - (N*q^2 + q)/ N\]     is 1/x or 1/5 or 0.2

        \[0.2 * 85 = x\] or               5 in this example

 

These are 3 separate groups of equations. They are separated by lines.

Edited by Trurl
Link to comment
Share on other sites

On 10/17/2021 at 9:43 PM, Trurl said:

The above equation should be close to zero

Why? 

 

On 10/17/2021 at 9:43 PM, Trurl said:

In the case where N = 85 and q = 17,

        

q2(Nq2+q)/N

    is 1/x or 1/5 or 0.2

 

What is the purpose? Note that [math]q^2-\frac{N q^2+q}{N}=-q/N[/math]

Link to comment
Share on other sites

Quote

   On 10/17/2021 at 3:43 PM,  Trurl said: 

The above equation should be close to zero

Why? 

Because it is p^2 minus p^2 derived.

Same with second equation. It is just how I derived the equations. Does it work? I don’t know. But I am simply comparing patterns in division.

Obviously you tried test values. Did it work with your values?

i will run more test values. Let me know if you have any more questions or your test values don’t work.

Link to comment
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now
 Share

×
×
  • Create New...

Important Information

We have placed cookies on your device to help make this website better. You can adjust your cookie settings, otherwise we'll assume you're okay to continue.