On the sequences ri, si, ti ∈ ℤ related to extended Euclidean algorithm and continued fractions
The extended Euclidean Algorithm is a practical technique used in many cryptographic applications, where it computes the sequences ri, si, ti ∈ ℤ that always satisfy ri = si a+ tib. The integer ri is the remainder in the ith sequences. The sequences si and ti arising from the extended Euclidean algo...
| Main Authors: | , |
|---|---|
| Format: | Conference or Workshop Item |
| Language: | English |
| Published: |
AIP Publishing
2016
|
| Online Access: | http://psasir.upm.edu.my/id/eprint/57195/ http://psasir.upm.edu.my/id/eprint/57195/1/On%20the%20sequences%20ri%2C%20si%2C%20ti%20%E2%88%88%20%E2%84%A4%20related%20to%20extended%20Euclidean%20algorithm%20and%20continued%20fractions.pdf |
| _version_ | 1848853297367089152 |
|---|---|
| author | Muhammad, Khairun Nisak Kamarulhaili, Hailiza |
| author_facet | Muhammad, Khairun Nisak Kamarulhaili, Hailiza |
| author_sort | Muhammad, Khairun Nisak |
| building | UPM Institutional Repository |
| collection | Online Access |
| description | The extended Euclidean Algorithm is a practical technique used in many cryptographic applications, where it computes the sequences ri, si, ti ∈ ℤ that always satisfy ri = si a+ tib. The integer ri is the remainder in the ith sequences. The sequences si and ti arising from the extended Euclidean algorithm are equal, up to sign, to the convergents of the continued fraction expansion of a/b. The values of (ri, si, ti) satisfy various properties which are used to solve the shortest vector problem in representing point multiplications in elliptic curves cryptography, namely the GLV (Gallant, Lambert & Vanstone) integer decomposition method and the ISD (integer sub decomposition) method. This paper is to extend the proof for each of the existing properties on (ri, si, ti). We also generate new properties which are relevant to the sequences ri, si, ti ∈ ℤ. The concepts of Euclidean algorithm, extended Euclidean algorithm and continued fractions are intertwined and the properties related to these concepts are proved. These properties together with the existing properties of the sequence (ri, si, ti) are regarded as part and parcel of the building blocks of a new generation of an efficient cryptographic protocol. |
| first_indexed | 2025-11-15T10:51:44Z |
| format | Conference or Workshop Item |
| id | upm-57195 |
| institution | Universiti Putra Malaysia |
| institution_category | Local University |
| language | English |
| last_indexed | 2025-11-15T10:51:44Z |
| publishDate | 2016 |
| publisher | AIP Publishing |
| recordtype | eprints |
| repository_type | Digital Repository |
| spelling | upm-571952017-09-08T10:29:58Z http://psasir.upm.edu.my/id/eprint/57195/ On the sequences ri, si, ti ∈ ℤ related to extended Euclidean algorithm and continued fractions Muhammad, Khairun Nisak Kamarulhaili, Hailiza The extended Euclidean Algorithm is a practical technique used in many cryptographic applications, where it computes the sequences ri, si, ti ∈ ℤ that always satisfy ri = si a+ tib. The integer ri is the remainder in the ith sequences. The sequences si and ti arising from the extended Euclidean algorithm are equal, up to sign, to the convergents of the continued fraction expansion of a/b. The values of (ri, si, ti) satisfy various properties which are used to solve the shortest vector problem in representing point multiplications in elliptic curves cryptography, namely the GLV (Gallant, Lambert & Vanstone) integer decomposition method and the ISD (integer sub decomposition) method. This paper is to extend the proof for each of the existing properties on (ri, si, ti). We also generate new properties which are relevant to the sequences ri, si, ti ∈ ℤ. The concepts of Euclidean algorithm, extended Euclidean algorithm and continued fractions are intertwined and the properties related to these concepts are proved. These properties together with the existing properties of the sequence (ri, si, ti) are regarded as part and parcel of the building blocks of a new generation of an efficient cryptographic protocol. AIP Publishing 2016 Conference or Workshop Item PeerReviewed application/pdf en http://psasir.upm.edu.my/id/eprint/57195/1/On%20the%20sequences%20ri%2C%20si%2C%20ti%20%E2%88%88%20%E2%84%A4%20related%20to%20extended%20Euclidean%20algorithm%20and%20continued%20fractions.pdf Muhammad, Khairun Nisak and Kamarulhaili, Hailiza (2016) On the sequences ri, si, ti ∈ ℤ related to extended Euclidean algorithm and continued fractions. In: 2nd International Conference on Mathematical Sciences and Statistics (ICMSS2016), 26-28 Jan. 2016, Kuala Lumpur, Malaysia. (pp. 1-8). 10.1063/1.4952482 |
| spellingShingle | Muhammad, Khairun Nisak Kamarulhaili, Hailiza On the sequences ri, si, ti ∈ ℤ related to extended Euclidean algorithm and continued fractions |
| title | On the sequences ri, si, ti ∈ ℤ related to extended Euclidean algorithm and continued fractions |
| title_full | On the sequences ri, si, ti ∈ ℤ related to extended Euclidean algorithm and continued fractions |
| title_fullStr | On the sequences ri, si, ti ∈ ℤ related to extended Euclidean algorithm and continued fractions |
| title_full_unstemmed | On the sequences ri, si, ti ∈ ℤ related to extended Euclidean algorithm and continued fractions |
| title_short | On the sequences ri, si, ti ∈ ℤ related to extended Euclidean algorithm and continued fractions |
| title_sort | on the sequences ri, si, ti ∈ ℤ related to extended euclidean algorithm and continued fractions |
| url | http://psasir.upm.edu.my/id/eprint/57195/ http://psasir.upm.edu.my/id/eprint/57195/ http://psasir.upm.edu.my/id/eprint/57195/1/On%20the%20sequences%20ri%2C%20si%2C%20ti%20%E2%88%88%20%E2%84%A4%20related%20to%20extended%20Euclidean%20algorithm%20and%20continued%20fractions.pdf |