Sign in to follow this  
Trurl

Prime Products just one last time

Recommended Posts

Trurl    12

Ok I wanted to see if this idea had any potential and I figured if it didn’t it would be shot down in a matter of minutes.

 

This is my final work on the Prime product problem.

 

I know it is just x^2 * y^2 = PNP^2

 

However the terms would just cancel out. Instead I have decided to let x^2 equal a pattern of x and PNP. So I just substituted the equation which is more complex and will not equal the right side of the equation for x^2.

 

In calculus where you have a complex derivative where you let du/dx equal a portion of the derivative so you can understand and simplify the manipulation of the integral. I am instead taking a more complex pattern and leaving it so x^2 does not cancel x squared. By doing this I hope it solves the pattern.

 

So if you could solve this polynomial equation you would solve the factorization problem.

 

If you couldn’t solve the polynomial? Well you could just write an algorithm that plugged in Prime numbers from smallest to largest. And because the polynomial is set up to find PNP you would get a feel for the range x was in. I mean, that this time when you try a number how far away the computed value is from PNP is significant.

So if this works it is faster than using division to factor.

 

But of course I await any disagreeing opinions. I now this problem gets that. But it was my final attempt before moving on to a different problem to pursue.

(((((x^2*PNP^4 + 2*PNP^2 * x^5) + x^8)/ 
       PNP^4 ) - ((1 - x^2/(2*PNP)))) * ((PNP^2/x^2 ))) == PNP^2





Above is the pattern of x^2 * y^2 = PNP^2

It is not to be simplified yet x put and tested in that place.

It is faster than division since the equation approaches PNP as the proper x is used. Smallest to largest Prime numbers are to be used.













PNP = 85
x = 5


(((((x^2*PNP^4 + 2*PNP^2 * x^5) + x^8)/ 
      PNP^4 ) - ((1 - x^2/(2*PNP)))) * ((PNP^2/x^2 ))) 




85

5

4179323/578

N[4179323/578, 14]

Sqrt[7230.66262975778546712802768166089965397924`14.]

85.033303062728








((((x^2*PNP^4 + 2*PNP^2 * x^5) + x^8)/ PNP^4 ) - ((1 - x^2/(2*PNP))))

4179323/167042

N[4179323/167042, 14]

25.019593874594









((PNP^2/x^2))

289



Questions to ask:
	Is it unique to factors of PNP or does it just give a decimal to all real numbers?
	
	Does it work for other values of PNP and x?
	
	Is it faster than factoring (recursion)?.
	
	Is it just x = x and as so not a useful pattern?
	
	Can the error be programmed?
	
	Verify then post. That is what I need to do. But I actually believe there is a pattern here.
	The question is does it work for all PNP and x values.
	
	I have many patterns. Some answer some of the questions. But I haven't found a polynomial
	I can solve after these questions have been answered. For example if this worked, I would need to 
	solve the given equation. And this proves to be challenging.






PNP = 85
x = 3


(((((x^2*PNP^4 + 2*PNP^2 * x^5) + x^8)/ 
      PNP^4 ) - ((1 - x^2/(2*PNP)))) * ((PNP^2/x^2 ))) 

85

3

847772947/130050

N[847772947/130050, 14]

6518.8231218762

Sqrt[6518.8231218762]

80.739229138481

Share this post


Link to post
Share on other sites
imatfaal    2477

You have the product and one of the factors - why are you not just dividing one by the other? In simple terms - without code and acronyms - what are you trying to do?

 

The tricky thing that will win a Field's Medal is if I give you a product of two large primes and you tell me quickly what those two large primes are - what you seem to be doing does not approximate or help with that.

Share this post


Link to post
Share on other sites
fiveworlds    67
if I give you a product of two large primes and you tell me quickly what those two large primes are

primeproduct = number.

 

If((product>file_get_contents(largest_prime_in_database)*file_get_contents(largest_prime_in_database))!==true)

{

if(file_exists(prime_product/primeproduct)){ echo file_get_contents(primeproduct);}

else {echo "That isn't a prime product";}

 

}

else{solve_new_primes();}

Share this post


Link to post
Share on other sites
imatfaal    2477

It is the final else that might perhaps cause difficulties :)

  • Upvote 1

Share this post


Link to post
Share on other sites
fiveworlds    67

Not really most calculators only go to 10 digits. Servers usually have a max int 2,147,483,647 . Javascript has a max int 2 ^ 53.

Edited by fiveworlds

Share this post


Link to post
Share on other sites
pzkpfw    164

Not really most calculators only go to 10 digits. Servers usually have a max int 2,147,483,647 . Javascript has a max int 2 ^ 53.

How long would it take for you to build the contents of your files?

 

The problem isn't about quick lookup, it's about the calculation.

 

 

(P.S. "!== true" is nasty, "=== false" would be slightly less nasty.)

Share this post


Link to post
Share on other sites
imatfaal    2477

Not really most calculators only go to 10 digits. Servers usually have a max int 2,147,483,647 . Javascript has a max int 2 ^ 53.

 

And the applications for these sorts of prime product factorisers tend to be looking at inputs of minimum 2^2048, and more likely quite a few orders higher. These are big numbers

How long would it take for you to build the contents of your files?

 

The problem isn't about quick lookup, it's about the calculation.

 

exactly - and the calculation is very very long; unless I lend you my quantum computer running Shor's Algorithm :)

  • Upvote 1

Share this post


Link to post
Share on other sites
Strange    2488

Not really most calculators only go to 10 digits. Servers usually have a max int 2,147,483,647 . Javascript has a max int 2 ^ 53.

 

 

That doesn't mean you can't write a program to handle numbers with a million digits.

Share this post


Link to post
Share on other sites
fiveworlds    67

That doesn't mean you can't write a program to handle numbers with a million digits

 

Why would you want to do that? The program would be terribly slow. The only use I know of for primeproducts is https on servers which are limited to 10 digits. The https cert can't be so complicated that a low end device like a phone can't use it for internet banking etc. The more complicated the cert the slower the page load times.

Edited by fiveworlds

Share this post


Link to post
Share on other sites
pzkpfw    164

Why would you want to do that? ...

For one thing - to win a prize :)https://en.wikipedia.org/wiki/Largest_known_prime_number

 

... not that I'm implying that Strange was only meaning Prime numbers.

 

 

(For the rest, you're doing that thing again where you do know about something, but then think that defines the entire problem space).

Share this post


Link to post
Share on other sites
imatfaal    2477

 

Why would you want to do that? The program would be terribly slow. The only use I know of for primeproducts is https on servers which are limited to 10 digits. The https cert can't be so complicated that a low end device like a phone can't use it for internet banking etc. The more complicated the cert the slower the page load times.

 

RSA encryption uses the product of two large primes.

 

10 digits? Seriously? - I could do that with a pencil and paper

Edited by imatfaal
typo

Share this post


Link to post
Share on other sites
Strange    2488

 

Why would you want to do that?

 

 

It is a good programming exercise. And there are plenty of applications where more precision is required than can be provided by ints or doubles.

 

 

 

The program would be terribly slow.

 

Well, you wouldn't use Javascript for a real application ...

 

FSA encryption uses the product of two large primes.

 

10 digits? Seriously? - I could do that with a pencil and paper

 

From Wikipedia:

 

RSA claims that 1024-bit keys are likely to become crackable some time between 2006 and 2010 and that 2048-bit keys are sufficient until 2030. An RSA key length of 3072 bits should be used if security is required beyond 2030.

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

 

Which implies the need to handle 1,000 digit numbers. (More if you are worried the NSA might be after you...)

Share this post


Link to post
Share on other sites
imatfaal    2477

 

 

It is a good programming exercise. And there are plenty of applications where more precision is required than can be provided by ints or doubles.

 

 

Well, you wouldn't use Javascript for a real application ...

 

From Wikipedia:

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

 

Which implies the need to handle 1,000 digit numbers. (More if you are worried the NSA might be after you...)

 

 

I think our system uses 2^4096. But as with all these systems the most obvious weakpoint is the warm thing between chair and screen.

 

security.png

  • Upvote 1

Share this post


Link to post
Share on other sites
Trurl    12

The equation is simply:

 

x^2 * y^2 = PNP^2

 

Which stands for:

 

p^2 * q^2 = N^2

 

 

The left side of the equation is x and y. (They are multiplied together to get PNP.)

 

The right side is PNP. Both sides squared of course.

 

 

I cannot solve this polynomial equation. If I could I would know instantly what x is.

 

However if values are tested starting with smaller Prime numbers, ( x is the smaller product), I believe you will have a feel for where x is because the equation with x plugged in will be approaching PNP (85 in this example).

 

I believe you could statistically use trial and error to find x. (As PNP approaches 85, x approaches 5.) You could change the equations to find y instead of x and use both the y and x versions to statistically eliminate products.

 

The question is does it work. I am not so much concerned with speed. I do not know how to program million digit numbers. But I think the larger the product the more valuable a statistically found solution is.

 

Of course if I could solve the polynomial (Which I can’t now, but I still have a few more tricks in my mathematical tool chest.) the problem would be solved. However I don’t claim this solution to be faster, but it represents a different approach.

 

I do however value feedback. Most people say this is stupid. I agree that the problem is impossible. I just had an idea for a different spin on it. I could use already discovered methods of evaluation, but other than the math lesson that would provide wouldn’t it just be doing the same thing and expecting different results. I approach this as a learning exercise. I have read much about cryptography and Mathematica.

 

In short if it’s wrong, it’s wrong. The only reason I put so much work into it is because I of my first idea that a logarithmic spiral could find a pattern in Prime numbers and maybe other sorts of patterns that seem to have no pattern.

 

So that is what I am trying to do. The only thing that would increase the speed of this equation would be a statistical (calculus) evaluation. If you test for x and it doesn’t equal PNP then you know if it is larger or smaller. Then you test again knowing that when x gets bigger, y gets smaller. So instead of making unlimited processes you can make an educated guess.

Share this post


Link to post
Share on other sites
imatfaal    2477

The equation is simply:

 

x^2 * y^2 = PNP^2

 

Which stands for:

 

p^2 * q^2 = N^2

 

 

The left side of the equation is x and y. (They are multiplied together to get PNP.)

 

The right side is PNP. Both sides squared of course.

why are you squaring both sides of this equation - it makes little difference (apart from opening a few changes to sign ie + / - )

if x*y=z

then (xy)^2=z^2

and of course x^2*y^2=z^2

 

 

 

I cannot solve this polynomial equation. If I could I would know instantly what x is.

 

NO you wouldn't - you have an equation with three unknowns. If you know one of them you only get the function of the other two - if you know two of them you know the third.

 

In the prime factoring problem YOU ONLY KNOW one - that is the product. If you knew two it would not be a problem - just a simple matter of division

 

 

 

However if values are tested starting with smaller Prime numbers, ( x is the smaller product), I believe you will have a feel for where x is because the equation with x plugged in will be approaching PNP (85 in this example).

 

I believe you could statistically use trial and error to find x. (As PNP approaches 85, x approaches 5.) You could change the equations to find y instead of x and use both the y and x versions to statistically eliminate products.

 

This is the crudest and longest sort of sieve - in effect you are just trying all primes (less than the largest prime which is smaller than the square root of the product) to see which works. The simplest way to do this is PNP/3 followed by PNP/5 f/b PNP/7 etc. You are doing this but making it very cumbersome

 

 

 

...Of course if I could solve the polynomial (Which I can’t now, but I still have a few more tricks in my mathematical tool chest.) the problem would be solved. However I don’t claim this solution to be faster, but it represents a different approach.

 

It is not different - it is merely a very round the houses and calculation intensive way of dividing by guesses; the quickest way to divide by guesses is to do just that.

 

If you were to demonstrate that some manipulation allowed a remainder which can be steadily gnawed away till you had an exact answer - that would be something special - BUT I promise at the moment your method does not do that; all it does is divide badly.

 

 

 

I do however value feedback. Most people say this is stupid. I agree that the problem is impossible. I just had an idea for a different spin on it. I could use already discovered methods of evaluation, but other than the math lesson that would provide wouldn’t it just be doing the same thing and expecting different results. I approach this as a learning exercise. I have read much about cryptography and Mathematica.

 

In short if it’s wrong, it’s wrong. The only reason I put so much work into it is because I of my first idea that a logarithmic spiral could find a pattern in Prime numbers and maybe other sorts of patterns that seem to have no pattern.

 

So that is what I am trying to do. The only thing that would increase the speed of this equation would be a statistical (calculus) evaluation. If you test for x and it doesn’t equal PNP then you know if it is larger or smaller. Then you test again knowing that when x gets bigger, y gets smaller. So instead of making unlimited processes you can make an educated guess.

 

But you cannot make an "educated guess"-

 

Boring and workable method - very slow

1 . you have a PNP of 1081

2. that is ALL you have (otherwise this is not the prime number factorisation problem)

3. divide by 3 - there is a remainder

4. divide by 5 - there is a remainder

5. ...etc

n. divide by 23 - there is no remainder and you have your other factor

 

your way

 

1. Do a horrendously complex iterated function on 1081 and 3 - find that it doesn't ever divide without a remainder

etc.

 

There is nothing in your operation by 3 that helps you get to "ah I should divide by 23" - and until you show that there is you are wasting your time.

 

You are NOT allowed to GUESS a test number to use in an operation with your PNP that you actually know is a factor - that is begging the question

  • Upvote 1

Share this post


Link to post
Share on other sites
Trurl    12

PNP = 85
x = 3


(((((x^2*PNP^4 + 2*PNP^2 * x^5) + x^8)/
PNP^4 ) - ((1 - x^2/(2*PNP)))) * ((PNP^2/x^2 )))

85

3

847772947/130050

N[847772947/130050, 14]

6518.8231218762

Sqrt[6518.82312187620146097654748173779315647828`14.]

80.739229138481









In[1]:=
PNP = 85
x = 7


(((((x^2*PNP^4 + 2*PNP^2 * x^5) + x^8)/
PNP^4 ) - ((1 - x^2/(2*PNP)))) * ((PNP^2/x^2 )))

Out[1]= 85

Out[2]= 7

Out[3]= 5538604027/708050

In[5]:= N[5538604027/708050, 14]

Out[5]= 7822.3346190241

In[6]:= Sqrt[7822.33461902408022032342348704187557375892`14.]

Out[6]= 88.443963157607




These values do not produce an N of 85. That is, we know the value of N. It is what was eliminated from the right side of the equation. So it is a significant value that is produced by the left hand side of the equation. 3 is 80.7 and 7 is 88.4 so the Prime number with the value closest to 85 (within a fraction of error) is 5.

Note the sides of the main equaiton are already squared in form. I did this to remove the square root. The values fo the equation reflect this.

A computer program could be written to test values based on the results of the left hand side of the equaiton. I know it isn't a perfect math solutions where I solved the polynomial but there is a distinction in the numbers. It tells the user if the number that was tested was too large or too small.

I will address more quesitons in a future post.







In[7]:=
PNP = 85
x = 5


(((((x^2*PNP^4 + 2*PNP^2 * x^5) + x^8)/
PNP^4 ) - ((1 - x^2/(2*PNP)))) * ((PNP^2/x^2 )))

Out[7]= 85

Out[8]= 5

Out[9]= 4179323/578

In[10]:= N[4179323/578, 14]

In[11]:= 7230.66262975778546712802768166089965397924`14.

Sqrt[7230.66262975778546712802768166089965397924`14.]

Out[11]= 7230.6626297578

Out[12]= 85.033303062728

Share this post


Link to post
Share on other sites
imatfaal    2477

PNP = 85

x = 3

...

 

Calc 85/3 = 28 1/3 ie not factor

 

 

 

 

PNP = 85

x = 7

 

calc 85/7 = 12 1/7 ie not a factor

 

 

 

PNP = 85

x = 5...

 

calc 85/5 = 17 ie prime factors found

 

That took me about a minute to work out in my head and type - and I got the answer. Your calculations are computational intensive and get to only an approximate result - WHY BOTHER?

 

You are NOT homing in on an answer - just going around the houses to get one you can find more easily.

 

If you don't understand what I mean by homing in on an answer above - or the iterative process I referred to in the previous post may I suggest you look at the Newtonian method for solving a quartic. That takes an initial guess and via the equation, its derivative, and a combination of both answers gives a closer answer; you then repeat with the closer answer; then you rinse and repeat. For the prime factorisation problem a new algorithm like this would be gold dust. But I repeat - YOURS DOES NOT DO THIS.

Share this post


Link to post
Share on other sites
Trurl    12

I know the equation is ugly. But what if such an equation existed how should it look?

 

I think the one advantage of my method is that it can be graphed.

 

I know that division is faster but I see advantages when working with larger numbers.

 

In your pen and paper estimates you know what to try but my method but mine is static in that it shows how far the tested number is from 85. Yes this has to be proved. This is the reason I share this post.

 

Of course this probably proves wrong. But sometimes you get gold fever and go looking for gold dust.

Share this post


Link to post
Share on other sites
Trurl    12

Wait a minute I decided it was simple logic. In your pen and paper your division does not show how close the calculation was to the correct factor. We know we are aiming for 85. This method shows 3 is below 85 and 7 is above.

 

Do you still think there is no pattern?

Share this post


Link to post
Share on other sites
imatfaal    2477

Trurl

 

Stop me when I say something you disagree with

 

1. We have the PNP nothing else.

2. We want p and q which are the prime numbers which when multiplied give the PNP

3. I do one calculation to show that 3 is not a divisor of PNP you do many. You do 12 operations to show 5 is likely a divisor - after 1 operation I know it is a factor

4. You do not get any hint from any of the incorrect choices of divisor about which new test divisor to try

5. You have to try all possible prime as your test divisor until you happen upon one which (kinda) works

 

Where is the time saving or increase in information?

 

Please try your method with a larger pair of primes which you do not (or at least pretend you do not) already know the factors of. And lose the pseudo code - write in mathematical terms; you need a simple algorithm that is quicker than dividing.

 

In your pen and paper your division does not show how close the calculation was to the correct factor.

 

No it doesn't but neither does yours! If you think it does - and claiming that on one example is a bit rich - can we have a longer example

Share this post


Link to post
Share on other sites
Trurl    12

I do not disagree. I do not have a way to mathematically solve this complex and ugly polynomial.

 

What I am saying is y has been eliminated from the equation. When you graph 85/x to find y both x and y are unknown. The quotient leaves no clue as to what values you are looking for.

 

When you graph the ugly left side of my equation x is still trial and error, but you are looking on the graph for 85^2 (or 85 if you graph the square root of the equation). The graph is a one to one and y increases as x increases. So when an x of 3 is 80 and x of 7 is 88 the x that is 85 is between them.

 

I prose using statics (calculus) to find the properties of the graph.

 

There isn't an advantage for an PNP of 85 but a large factor where factoring is difficult my method may prove useful.

 

But I do not how to program million digit numbers.

 

But do you agree if you use trail and error, you are approaching the known PNP and at least know that your x is larger or smaller than the x which is the factor? That is something division alone does not show.

Share this post


Link to post
Share on other sites
Trurl    12

Did anyone agree or disagree with my last post?

 

Obviously the odds are against breaking a one way function. But if you feel it doesn’t work please be my guest to call me stupid. Shooting an idea down is better than no response at all. I am serious in my attempts and have other equations or patterns in products.

 

I also need guidance on how to program numbers. I mean recursive factoring. Traditionally large numbers are difficult to program. Mathematica can handle about 300 digits.

 

So proceed to disprove this problem if you decide it needs bashing.

 

Here is another pattern that I believe to be unique of Prime Products. It is simpler than the last, but still complex to solve the polynomial.

Many of the equations or patterns as I call them are true for all x and y. However there are some (though complex) patterns are only true to Prime factors as shown below. There are several with one from the last work to this one giving us 2 complicated but true patterns.





y = ((PNP^4/x + 2* (PNP^2 * x^2) + x^5) / PNP^3)




I believe this equation to be a pattern of multiplication to solve for a y that is unique, that is it doesn't prove always true with all x's.





x * y = PNP

x * ((PNP^4/x + 2* (PNP^2 * x^2) + x^5) / PNP^3) = PNP

or another equation y = y

((PNP^4/x + 2* (PNP^2 * x^2) + x^5) / PNP^3) == PNP/x




I will continue to find errors in my equations and post those that are unique to Prime factors. Maybe a simpler mathematical equation can be found.




With error :
  
  

x * ( ((PNP^4/x + 2* (PNP^2 * x^2) + x^5) / PNP^3) - 2*(x^2/PNP) ) = PNP

Share this post


Link to post
Share on other sites
Trurl    12

I don't know the speed. But Mathematica can draw graphs fast. I am looking for some guidance on how to program numbers of hundreds of digits.

 

 

See for yourself on the code and attachments that these 2 equations work with large values. So if you agree or disagree just post here.

 

 

I am researching ways to use calculus on the graphs and also have other methods of solving the polynomials.

 

Here is my results of my last effort that has changed from finding patterns in Prime multiplication to solving the found polynomial equations.

In[32]:= PNP = 7727* 65537
t = 7727
 
Sqrt[(((((t^2*PNP^4 + 2*PNP^2 * t^5) + t^8)/ 
       PNP^4 ) - ((1 - t^2/(2*PNP)))) * ((PNP^2/t^2 ))) ]


 t * ( ((PNP^4/t + 2* (PNP^2 *t^2) + t^5) / PNP^3) - 2*(t^2/PNP) )

Out[32]= 506404399

Out[33]= 7727

Out[34]= (11 Sqrt[18205987286897013994227797/2])/65537

In[36]:= N[(11 Sqrt[18205987286897013994227797/2])/65537, 14]

Out[36]= 5.0640530604466*10^8















Out[30]= 142546691485720530013630/281487861809153

In[31]:= N[142546691485720530013630/281487861809153]

Out[31]= 5.06404*10^8

SFN_PatternsPDFHigherValues.pdf

SFN_PatternsPDFHigherValuesb.pdf

Share this post


Link to post
Share on other sites
Strange    2488

 

I don't know the speed. But Mathematica can draw graphs fast. I am looking for some guidance on how to program numbers of hundreds of digits.

 

 

There are standard libraries for this. For example: https://gmplib.org

Share this post


Link to post
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

Sign in to follow this