Results 1 to 11 of 11

Thread: Fibonacci and Primes

  1. #1

    Fibonacci and Primes

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

  2. #2
    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.

  3. #3
    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.
    Last edited by Aquatic; April 11th, 2006 at 04:59.

  4. #4
    הבּרוּ נשׂאי כּלי יהוה mike's Avatar
    Join Date
    Mar 2001
    Posts
    491
    http://www.math.temple.edu/~renault/fibonacci/thesis.html

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

  6. #6
    הבּרוּ נשׂאי כּלי יהוה mike's Avatar
    Join Date
    Mar 2001
    Posts
    491
    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

  7. #7
    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.
    Last edited by Admiral; May 27th, 2006 at 22:13.

  8. #8
    Administrator dELTA's Avatar
    Join Date
    Oct 2000
    Location
    Ring -1
    Posts
    4,206
    Blog Entries
    5
    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.

  9. #9
    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?

  10. #10
    הבּרוּ נשׂאי כּלי יהוה mike's Avatar
    Join Date
    Mar 2001
    Posts
    491
    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

  11. #11
    הבּרוּ נשׂאי כּלי יהוה mike's Avatar
    Join Date
    Mar 2001
    Posts
    491
    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.

Bookmarks

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •