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.

--
[email protected] | sybershock.com | sci.crypt

--- SoupGate-Win32 v1.05
* Origin: fsxNet Usenet Gateway (21:1/5)

Montgomery Schorr

Not a star wars character.


Peter Fairbrother


On 11/04/2024 14:35, SugarBug wrote:

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.

--- SoupGate-Win32 v1.05
* Origin: fsxNet Usenet Gateway (21:1/5)

On Fri, 12 Apr 2024 16:18:57 -0500
SugarBug <[email protected]> wrote:

On Thu, 11 Apr 2024 19:18:45 +0100
Peter Fairbrother <[email protected]> wrote:

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

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.

--
[email protected] | sybershock.com | sci.crypt

--- SoupGate-Win32 v1.05
* Origin: fsxNet Usenet Gateway (21:1/5)

On Thu, 11 Apr 2024 19:18:45 +0100
Peter Fairbrother <[email protected]> wrote:

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

--
[email protected] | sybershock.com | sci.crypt

--- SoupGate-Win32 v1.05
* Origin: fsxNet Usenet Gateway (21:1/5)

SugarBug <[email protected]> writes:

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

...

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
--
We are no longer hunters and nomads. No longer awed and frightened, as we have gained some understanding of the world in which we live. As such, we can cast aside childish remnants from the dawn of our civilization.
-- NotSanguine on SoylentNews, after Eugen Weber in /The Western Tradition/

--- SoupGate-Win32 v1.05
* Origin: fsxNet Usenet Gateway (21:1/5)