Fast Modular Exponentiation with Huge Exponents

[SugarBug]

I am seeking different efficient programming methods (algorithms) for modular exponentiation with huge exponents, viz. 160-bit to 1024-bit integers as exponents and bases. I hope to find something a bit better than repeated squaring to handle the exponent; or at least a better way of chunking it. I will be working with DWORD and QWORD segments, so this should be an interesting hack.

Example:

1376059935759825045063891486059888763810529472911 ^
1227306356230802884842928886716272231596711085779 %
1393133130738640234978081120598228122485209166367

Imagine instead of 160 bits up to to 1024 bits for all integers in the equation, the base, exponent, and modulus.

I am not the least bit interested in using 3rd party code for this project. Please point the way to _algorithms_, not libraries or units.

[Peter Fairbrother]

Montgomery Schorr

Not a star wars character.


Peter Fairbrother

Post by SugarBug
I am seeking different efficient programming methods (algorithms) for modular exponentiation with huge exponents, viz. 160-bit to 1024-bit integers as exponents and bases. I hope to find something a bit better than repeated squaring to handle the exponent; or at least a better way of chunking it. I will be working with DWORD and QWORD segments, so this should be an interesting hack.
1376059935759825045063891486059888763810529472911 ^
1227306356230802884842928886716272231596711085779 %
1393133130738640234978081120598228122485209166367
Imagine instead of 160 bits up to to 1024 bits for all integers in the equation, the base, exponent, and modulus.
I am not the least bit interested in using 3rd party code for this project. Please point the way to _algorithms_, not libraries or units.

[SugarBug]

On Fri, 12 Apr 2024 16:18:57 -0500

On Thu, 11 Apr 2024 19:18:45 +0100

Post by Peter Fairbrother
Montgomery Schorr

Do you mean "Scnorr" as in CP Schnorr Signatures?
https://scholar.google.com/scholar?hl=en&as_sdt=0%2C4&q=montgomery+exponentiation&btnG=&oq=%22Montgomery%22+expon
https://scholar.google.com/scholar?hl=en&as_sdt=0%2C4&q=schnorr+exponentiation

Currently I am looking at Montgomery and Joye ladders and division chains. I hope to find some really exotic ideas to play with. I have been playing with some simple primitives that work with small exponents, but fall apart with large powers.

[SugarBug]

On Thu, 11 Apr 2024 19:18:45 +0100

Post by Peter Fairbrother
Montgomery Schorr

Do you mean "Scnorr" as in CP Schnorr Signatures?

Do you mean like this:

https://scholar.google.com/scholar?hl=en&as_sdt=0%2C4&q=montgomery+exponentiation&btnG=&oq=%22Montgomery%22+expon

And this:

https://scholar.google.com/scholar?hl=en&as_sdt=0%2C4&q=schnorr+exponentiation

[Phil Carmody]

Post by SugarBug
I am seeking different efficient programming methods (algorithms) for
modular exponentiation with huge exponents, viz. 160-bit to 1024-bit

...

Post by SugarBug
I am not the least bit interested in using 3rd party code for this
project. Please point the way to _algorithms_, not libraries or units.

/Prime Numbers and Computer Methods for Factorization/ - Hans Riesel
/Prime Numbers: A Computational Perspective/ - Crandall & Pomerance

Phil