PDA

View Full Version : Fibonacci and Primes

Aquatic
March 16th, 2006, 02:47

March 16th, 2006, 09:31
With all that beautiful mathematics out there, why did we all end up using number theory? I think it's such a revolting, inelegant, almost arbitrary study.
One day I'll come up with a cipher based on complex analysis or nonlinear theory. That way we won't all have to hit the gin when faced with the task of coding an encrypter.
[/rant]

But yes, as numbers go, the Fibonacci sequence is pretty nifty. I've noticed that it's difficult to find any decent material among 'popular maths' sites these days, so this page is a good find.

Aquatic
April 11th, 2006, 04:38
What do you guys think of a relationship between primes and the fibonacci sequence?

Fibonacci is a sequence of nature, in a way it is a sort of natural law, and ordering of things. Maybe primes play a similar role in nature.

People often talk about the Fibonacci Spiral, and the Phi Spiral. The Phi spiral is considered the perfect one, and the Fibonacci Spiral is the one that is almost perfect. The Fibonacci spiral tries to approximate the Phi Spiral.

Primes also have a spiral, called the "Ulam spiral", but I don't know if that has a connection with the Phi/Fibonacci spirals.

Primes in Sunflower spiral
http://www.pitt.edu/AFShome/d/i/dickinsm/public/html/1020-061/sunflower.html

Fibonacci and seed arrangement on flower heads (including the sunflower)
http://www.mcs.surrey.ac.uk/Personal/R.Knott/Fibonacci/fibnat.html#seeds

I don't know if there is a connection between a prime spiral and a fibonacci spiral, but it makes you wonder. Maybe sunflowers can show us some connection between primes and fibonacci.

mike
May 17th, 2006, 23:49
http://www.math.temple.edu/~renault/fibonacci/thesis.html

Aquatic
May 25th, 2006, 18:48
If there is a significant connection between fibonacci and primes, then what are the implications for cryptography?

mike
May 26th, 2006, 18:27
It means you can do a version of RSA on fibonacci numbers instead of the normal way, multiplying indices instead of exponents. Lucas numbers obey the same recursion (L[N] = L[N-1]+L[N-2]) but have different initial conditions. There's a public-key algorithm called LUC that does this; the inventor thinks its the greatest thing since sliced bread, but it's just RSA over a subgroup of the multiplicative group of F_{p^2} rather than over the multiplicative group Z/pqZ.

http://www.ddj.com/article/printableArticle.jhtml?articleID=184408922&dept_url=/
http://www.ssh.com/support/cryptography/algorithms/asymmetric.html

May 27th, 2006, 09:31
You a mathematician, mike?

But indeed, the two systems are essentially isomorphic. Only, modular exponentiation can be computed very quickly, whereas manipulating Fibonacci numbers is a little unwieldy by comparison.
The implications are many, but none of them profound. The crunch, as always, comes down to factorising integers.

Regards

Edit: Ambiguous sentences are as bad as false ones.

dELTA
May 28th, 2006, 10:45
Quote:
 You a mathematician, mike?
Hehe, bet yo' ass he is, and quite a disgustingly good one too. He's our resident math and crypto god.

Aquatic
June 5th, 2006, 06:17
Today I watched the movie "Pi" again: http://www.imdb.com/title/tt0138704/

I'm not sure why he called the movie Pi, because it seemed like the movie was much more focused on phi and fibonacci. Maybe he thought that Pi was more familiar to people.

Mike, I meant could a connection between fibonnaci and primes make RSA easier to solve?

mike
June 7th, 2006, 16:58
Quote:
 [Originally Posted by dELTA]Hehe, bet yo' ass he is, and quite a disgustingly good one too. He's our resident math and crypto god.

Well, if I'm a god, then it's just a minor house deity! There are a lot better mathematicians out there; they just don't hang out on RCE boards. And every other moderator on this board is a better reverse engineer--I just happen to have some crypto experience.

Here's my homepage: http://math.ucr.edu/~mike

mike
June 7th, 2006, 17:01
Quote:
 [Originally Posted by Aquatic]Today I watched the movie "Pi" again: http://www.imdb.com/title/tt0138704/

Have you seen the music video "Experimental film?"
http://www.homestarrunner.com/expfilm.html
It's as though it was written as a parody of Pi.

Quote:
 [Originally Posted by Aquatic]Mike, I meant could a connection between fibonnaci and primes make RSA easier to solve?

Maybe, but no one knows about one that does. And if there is, it's likely to be closely related to the links I posted.