An interesting read: http://www.mcs.surrey.ac.uk/Personal/R.Knott/Fibonacci/fibmaths.html#fibprimes

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.

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.

What I found interesting was this page:
Primes in Sunflower spiral
http://www.pitt.edu/AFShome/d/i/dickinsm/public/html/1020-061/sunflower.html

Then look at this page:
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.

http://www.math.temple.edu/~renault/fibonacci/thesis.html

If there is a significant connection between fibonacci and primes, then what are the implications for cryptography?

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

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
Admiral

Edit: Ambiguous sentences are as bad as false ones.

Hehe, bet yo' ass he is, and quite a disgustingly good one too. He's our resident math and crypto god.

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?

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

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.


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.