Fibonacci number certificates

Suppose I give you a big numberF and claim thatF is a Fibonacci number. How could you confirm this?

Before I go further, let me say what this post is really about. It's not about Fibonacci numbers so much as it is about proofs and certificates. There's no market for large Fibonacci numbers, and certainly no need to quickly verify that a number is a Fibonacci number.

You could write a program to generate Fibonacci numbers, and run it until it either producesF , in which case you knowF is a Fibonacci number, or the program produces a larger number thanF without having producedF, in which case you know it's not a Fibonacci number. But there's a faster way.

A certificate is data that allows you to confirm a solution to a problem in less time, usually far less time, than it took to generate the solution. For example, Pratt certificates give you a way to prove that a number is prime. For a large prime, you could verify its Pratt certificate much faster than directly trying to prove the number is prime.

There is a theorem that says a numberf is a Fibonacci number if and only if one of 5f² 4 is a perfect square. So in addition to F another numberr that is a certificate thatF is a Fibonacci number. You compute

N = 5F^2 - r^2

and if N is equal to 4 or -4, you know that F is a Fibonacci number. Otherwise it is not.

Here's a small example. Suppose I give you (12586269025, 28143753123) and claim that the first number is a Fibonacci number and the second number is its certificate. You can compute

5 * 12586269025^2 - 28143753123^2

and get -4, verifying the claim.

Certificates are all about the amount of computation the verifier needs to do. The prover, i.e. the person producing the certificate, has to do extra work to provide a certificate in addition to a problem solution. This trade-off is acceptable, for example, in a blockchain where a user posts one transaction but many miners will verify many transactions.

Related posts

• Elliptic curve primality certificates
• Generation versus verification costs
• Proof of optimization
• Zero knowledge proof of compositeness

The post Fibonacci number certificates first appeared on John D. Cook.