An average case efficient algorithm for solving two-variable linear Diophantine equations
Fuente:
arXiv
Saved in:
| Main Authors: | , |
|---|---|
| Format: | Preprint |
| Published: |
2024
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866913008333094912 |
|---|---|
| author | Deora, Mayank Pal, Pinakpani |
| author_facet | Deora, Mayank Pal, Pinakpani |
| contents | Solving two-variable linear Diophantine equations has applications in many cryptographic protocols such as RSA and Elliptic curve cryptography. The Extended Euclid's algorithm is a well known algorithm to solve these equations. We revisit two algorithms to solve two-variable linear Diophantine equations. We write the iterative version of one of the revisited algorithms. For another, we do a fine-grained analysis of the number of recursive calls and arrive at a periodic function that represents the number of recursive calls. We find the period and use it to derive multiple upper bounds on the average number of recursive calls. The upper bounds conclude that the average number of recursive calls in the analyzed algorithm is a constant term improvement over the Extended Euclid's algorithm. We propose an iterative variant of the algorithm. We implement this algorithm and find that the average number of iterations by our algorithm is less than that of two existing algorithms. We compare the number of iterations in this algorithm and in Extended Euclid's algorithm. In the comparison, we find that for 100\% of the solvable instances of inputs, the iterations are less than that in Extended Euclid's algorithm. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2409_14052 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | An average case efficient algorithm for solving two-variable linear Diophantine equations Deora, Mayank Pal, Pinakpani Cryptography and Security Data Structures and Algorithms Number Theory Solving two-variable linear Diophantine equations has applications in many cryptographic protocols such as RSA and Elliptic curve cryptography. The Extended Euclid's algorithm is a well known algorithm to solve these equations. We revisit two algorithms to solve two-variable linear Diophantine equations. We write the iterative version of one of the revisited algorithms. For another, we do a fine-grained analysis of the number of recursive calls and arrive at a periodic function that represents the number of recursive calls. We find the period and use it to derive multiple upper bounds on the average number of recursive calls. The upper bounds conclude that the average number of recursive calls in the analyzed algorithm is a constant term improvement over the Extended Euclid's algorithm. We propose an iterative variant of the algorithm. We implement this algorithm and find that the average number of iterations by our algorithm is less than that of two existing algorithms. We compare the number of iterations in this algorithm and in Extended Euclid's algorithm. In the comparison, we find that for 100\% of the solvable instances of inputs, the iterations are less than that in Extended Euclid's algorithm. |
| title | An average case efficient algorithm for solving two-variable linear Diophantine equations |
| topic | Cryptography and Security Data Structures and Algorithms Number Theory |
| url | https://arxiv.org/abs/2409.14052 |