How do I know how many iterations an arbitrary extended gcd algorithm would take?

Question

If I don't know anything about the numbers for which I am egcd'ing, can I make a reasonable numerical value to the maximum number of iterations it will take?

I have a question that involves me figuring out if an RSA public key comprised of just one prime p (instead of the typical pq) works. Meaning, I have to figure out if an outsider is able to decode it, knowing what N and e are. One of the steps would be finding d, through egcd. Knowing the number of iterations it could take would help but I'm stuck

Also we're assuming the eavesdropper (Eve) knows N=p

Answer 1

The worst case number iterations is one greater than the ordinal number of the Fibonacci number just greater than the second number entered into Euclid's algorithm. Here is an example of a program run that tests the iterations of all combinations from $1$ to $1000$. (Note here that 2 is considered to be the third Fibonacci number.) The iteration count is not displayed until it reaches just greater than the previous greatest iteration count. (Note: the count will be one greater if the larger number is entered second.)

 iterations( 1 )  GCD( 2 , 1 ) = 1 
 iterations( 2 )  GCD( 3 , 2 ) = 1 
 iterations( 3 )  GCD( 5 , 3 ) = 1 
 iterations( 4 )  GCD( 8 , 5 ) = 1 
 iterations( 5 )  GCD( 13 , 8 ) = 1 
 iterations( 6 )  GCD( 21 , 13 ) = 1 
 iterations( 7 )  GCD( 34 , 21 ) = 1 
 iterations( 8 )  GCD( 55 , 34 ) = 1 
 iterations( 9 )  GCD( 89 , 55 ) = 1 
 iterations( 10 )  GCD( 144 , 89 ) = 1 
 iterations( 11 )  GCD( 233 , 144 ) = 1 
 iterations( 12 )  GCD( 377 , 233 ) = 1 
 iterations( 13 )  GCD( 610 , 377 ) = 1 
 iterations( 14 )  GCD( 987 , 610 ) = 1