Alina Matyukhina

Efficient Algorithm for Divisibility Discovery on Recursive Sequences Alina Matyukhina

Many cryptographic protocols are based on the complexity of prime factorization large integers ?for example, the RSA problem. When the numbers are very large, no efficient, non-quantum integer factorization algorithm is known. On other hand we have computational complexity of the Fibonacci sequence and recursive sequences in all, as the members of sequences can reach millions. Can we combine two concepts to investigate the unsolved problem in computer science? This book deals with the theoretical and the computational aspects of the divisibility of recursive sequence elements by primes, which is defined by discriminant of characteristic equation D. Depending on whether D -quadratic residue in the field of residues modulo p, we derived two theorems that helps you specify the elements of this sequence, which is divisible by primes. The algorithm and structural computer program were developed, it doesn't require the additional calculation of the members of the sequences, therefore it reduces time to fulfill the task. These methods were applied to the solution of problems on divisibility. The book presents the generalization of International Mathematical Olympiad tasks.