Math Is Fun Forum

  Discussion about math, puzzles, games and fun.   Useful symbols: ÷ × ½ √ ∞ ≠ ≤ ≥ ≈ ⇒ ± ∈ Δ θ ∴ ∑ ∫ • π ƒ -¹ ² ³ °

You are not logged in.

#1 2015-11-20 08:16:08

blackcap
Member
Registered: 2015-11-20
Posts: 7

Fancy curves, and the n=p*q problem

Many cryptography algorithms - notable RSA - rely on the difficulty of factorizing semiprimes. Essentially, the server multiplies two gigantic primes and send you the result, you use that number to encrypt your message, and the only way to decrypt it is to know the two original primes.

So the server sends you a number n. n = p*q, where p and q are primes.
You can consider p and q to be the length of the short sides on a right angled triangle, and if we where to know the angle of either A or B we could figure out p and q.

p = sqrt (n * tan(((pi*A)/180)))
q = sqrt (n / tan(((pi*B)/180)))

If you plot those functions you'll get this:

QzA8JCO.png

The point where the two curves crosses is sqrt(n). At either side of x=45, the only point where the two curves travel trough a integer value on the y-axis at same place on the x-axis, is at the two original factors p and q.

Now this is where I need help. It looks as if I where to invert either of the curves, they would intersect at the point of the factors. I made this mockup to illustrate this:

dy0JKGt.png

How do I invert the curves, and do they actually intersect at the factors?

Last edited by blackcap (2015-11-20 08:18:22)

Offline

#2 2015-11-20 11:50:50

bobbym
bumpkin
From: Bumpkinland
Registered: 2009-04-12
Posts: 109,606

Re: Fancy curves, and the n=p*q problem

I have placed your images in.

Is that Geogebra? What version?


In mathematics, you don't understand things. You just get used to them.
If it ain't broke, fix it until it is.
Always satisfy the Prime Directive of getting the right answer above all else.

Offline

#3 2015-11-21 01:19:53

Bob
Administrator
Registered: 2010-06-20
Posts: 10,053

Re: Fancy curves, and the n=p*q problem

hi blackcap,

Welcome to the forum.

What do you mean by inversion?

In 'real' encryption the value of n is a lot bigger.  Graph plotting may not be sufficiently accurate to determine the factors.  Actually, I hope this is the case (sorry) or it blows a hole in encryption and I'm quite keen that we can continue using it for a while yet.  smile

Bob


Children are not defined by school ...........The Fonz
You cannot teach a man anything;  you can only help him find it within himself..........Galileo Galilei
Sometimes I deliberately make mistakes, just to test you!  …………….Bob smile

Offline

#4 2015-11-21 03:22:43

blackcap
Member
Registered: 2015-11-20
Posts: 7

Re: Fancy curves, and the n=p*q problem

If you where to place a mirror vertically such that it is on top of both B and D or A and C, the reflection of the curve would intersect with the real curve at the factor points. It looks as if this might be the case even if you don't deliberately position the mirror on top of the points.

It is the web version of geogebra, you don't even have to download it these days: web.geogebra.org/

Offline

#5 2015-11-21 13:24:07

Agnishom
Real Member
From: Riemann Sphere
Registered: 2011-01-29
Posts: 24,974
Website

Re: Fancy curves, and the n=p*q problem

You need to explain what these curves actually mean


'And fun? If maths is fun, then getting a tooth extraction is fun. A viral infection is fun. Rabies shots are fun.'
'God exists because Mathematics is consistent, and the devil exists because we cannot prove it'
I'm not crazy, my mother had me tested.

Offline

#6 2015-11-22 04:10:20

blackcap
Member
Registered: 2015-11-20
Posts: 7

Re: Fancy curves, and the n=p*q problem

Agnishom wrote:

You need to explain what these curves actually mean

So you have a number n, that is equal to p*q. You don't know what p and q are, but you know n, and you know that both p and q are primes.
Say that we consider p and q to be the short sides of a right angled triangle. Then n/2 would be area of the triangle, and we know that one angle is 90.
If we where to find another angle, p, q, or the hypotenuse, we could figure out what p and q are!

The plot is just all possible values for the angles:

We can say that:
1) tan(a) = p/q
2) T = (p*q)/2
which means that
3) q = 2T/p
and if we substitute this into (1), we get:
4) tan(a) = p/(2T/q) = p^2/2T
and: p^2 = 2T * tan(a)

pi/180 is just to convert from angles to radians for geogebra, and the green curve is: f(x) = sqrt ( n * tan((pi*x)/180) )

Last edited by blackcap (2015-11-22 04:17:15)

Offline

Board footer

Powered by FluxBB