Rocksolid Light

News from da outaworlds

mail  files  register  groups  login

Message-ID:  

Fame is a vapor; popularity an accident; the only earthly certainty is oblivion. -- Mark Twain

sci / sci.crypt / Fast Modular Exponentiation with Huge Exponents

SubjectAuthor
* Fast Modular Exponentiation with Huge ExponentsSugarBug
+* Re: Fast Modular Exponentiation with Huge ExponentsPeter Fairbrother
|`* Re: Fast Modular Exponentiation with Huge ExponentsSugarBug
| `- Re: Fast Modular Exponentiation with Huge ExponentsSugarBug
`- Re: Fast Modular Exponentiation with Huge ExponentsPhil Carmody

1
Subject: Fast Modular Exponentiation with Huge Exponents
From: SugarBug
Newsgroups: sci.crypt
Organization: Baggy Jeans Mafia (sybershock.com)
Date: Thu, 11 Apr 2024 13:35 UTC
Path: eternal-september.org!news.eternal-september.org!feeder3.eternal-september.org!i2pn.org!i2pn2.org!.POSTED!not-for-mail
From: 3883@sugar.bug (SugarBug)
Newsgroups: sci.crypt
Subject: Fast Modular Exponentiation with Huge Exponents
Date: Thu, 11 Apr 2024 08:35:22 -0500
Organization: Baggy Jeans Mafia (sybershock.com)
Message-ID: <b1fbf007d052918737b3ad5b1987fa27$1@sybershock.com>
MIME-Version: 1.0
Content-Type: text/plain; charset=US-ASCII
Content-Transfer-Encoding: 7bit
Injection-Info: i2pn2.org;
logging-data="823606"; mail-complaints-to="usenet@i2pn2.org";
posting-account="yZybWhCr+jI4C3MuGpPde+DhCwsjQrVZrsCOigcx7fM";
X-Newsreader: 3883.7766
X-Spam-Checker-Version: SpamAssassin 4.0.0
View all headers

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.

--
3883@sugar.bug | sybershock.com | sci.crypt

Subject: Re: Fast Modular Exponentiation with Huge Exponents
From: Peter Fairbrother
Newsgroups: sci.crypt
Organization: A noiseless patient Spider
Date: Thu, 11 Apr 2024 18:18 UTC
References: 1
Path: eternal-september.org!news.eternal-september.org!.POSTED!not-for-mail
From: peter@tsto.co.uk (Peter Fairbrother)
Newsgroups: sci.crypt
Subject: Re: Fast Modular Exponentiation with Huge Exponents
Date: Thu, 11 Apr 2024 19:18:45 +0100
Organization: A noiseless patient Spider
Lines: 22
Message-ID: <uv99i5$1qt74$1@dont-email.me>
References: <b1fbf007d052918737b3ad5b1987fa27$1@sybershock.com>
MIME-Version: 1.0
Content-Type: text/plain; charset=UTF-8; format=flowed
Content-Transfer-Encoding: 7bit
Injection-Date: Thu, 11 Apr 2024 20:18:45 +0200 (CEST)
Injection-Info: dont-email.me; posting-host="d84b62fbd70cdcf02ad3ac12d7dba30b";
logging-data="1930468"; mail-complaints-to="abuse@eternal-september.org"; posting-account="U2FsdGVkX1+UInakHo1AYDo7Uv5GfumHV4tcYYEMV7w="
User-Agent: Mozilla Thunderbird
Cancel-Lock: sha1:BZLnWVZqDR32zMJjdok3iQnuvTU=
Content-Language: en-GB
In-Reply-To: <b1fbf007d052918737b3ad5b1987fa27$1@sybershock.com>
View all headers

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.
>

Subject: Re: Fast Modular Exponentiation with Huge Exponents
From: SugarBug
Newsgroups: sci.crypt
Organization: Baggy Jeans Mafia (sybershock.com)
Date: Fri, 12 Apr 2024 21:18 UTC
References: 1 2
Path: eternal-september.org!news.eternal-september.org!feeder3.eternal-september.org!i2pn.org!i2pn2.org!.POSTED!not-for-mail
From: 3883@sugar.bug (SugarBug)
Newsgroups: sci.crypt
Subject: Re: Fast Modular Exponentiation with Huge Exponents
Date: Fri, 12 Apr 2024 16:18:57 -0500
Organization: Baggy Jeans Mafia (sybershock.com)
Message-ID: <1300f6a02db54d21493db5d602400813$1@sybershock.com>
References: <b1fbf007d052918737b3ad5b1987fa27$1@sybershock.com>
<uv99i5$1qt74$1@dont-email.me>
MIME-Version: 1.0
Content-Type: text/plain; charset=US-ASCII
Content-Transfer-Encoding: 7bit
Injection-Info: i2pn2.org;
logging-data="975142"; mail-complaints-to="usenet@i2pn2.org";
posting-account="yZybWhCr+jI4C3MuGpPde+DhCwsjQrVZrsCOigcx7fM";
X-Spam-Checker-Version: SpamAssassin 4.0.0
X-Newsreader: 3883.7766
View all headers

On Thu, 11 Apr 2024 19:18:45 +0100
Peter Fairbrother <peter@tsto.co.uk> 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

--
3883@sugar.bug | sybershock.com | sci.crypt

Subject: Re: Fast Modular Exponentiation with Huge Exponents
From: SugarBug
Newsgroups: sci.crypt
Organization: Baggy Jeans Mafia (sybershock.com)
Date: Fri, 12 Apr 2024 21:27 UTC
References: 1 2 3
Path: eternal-september.org!news.eternal-september.org!feeder3.eternal-september.org!i2pn.org!i2pn2.org!.POSTED!not-for-mail
From: 3883@sugar.bug (SugarBug)
Newsgroups: sci.crypt
Subject: Re: Fast Modular Exponentiation with Huge Exponents
Date: Fri, 12 Apr 2024 16:27:48 -0500
Organization: Baggy Jeans Mafia (sybershock.com)
Message-ID: <47132d46cb2d382cdc1dd7cbca86b44d$1@sybershock.com>
References: <b1fbf007d052918737b3ad5b1987fa27$1@sybershock.com>
<uv99i5$1qt74$1@dont-email.me>
<1300f6a02db54d21493db5d602400813$1@sybershock.com>
MIME-Version: 1.0
Content-Type: text/plain; charset=US-ASCII
Content-Transfer-Encoding: 7bit
Injection-Info: i2pn2.org;
logging-data="975142"; mail-complaints-to="usenet@i2pn2.org";
posting-account="yZybWhCr+jI4C3MuGpPde+DhCwsjQrVZrsCOigcx7fM";
X-Spam-Checker-Version: SpamAssassin 4.0.0
X-Newsreader: 3883.7766
View all headers

On Fri, 12 Apr 2024 16:18:57 -0500
SugarBug <3883@sugar.bug> wrote:

> On Thu, 11 Apr 2024 19:18:45 +0100
> Peter Fairbrother <peter@tsto.co.uk> 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.

--
3883@sugar.bug | sybershock.com | sci.crypt

Subject: Re: Fast Modular Exponentiation with Huge Exponents
From: Phil Carmody
Newsgroups: sci.crypt
Organization: A noiseless patient Spider
Date: Tue, 16 Apr 2024 09:24 UTC
References: 1
Path: eternal-september.org!news.eternal-september.org!.POSTED!not-for-mail
From: pc+usenet@asdf.org (Phil Carmody)
Newsgroups: sci.crypt
Subject: Re: Fast Modular Exponentiation with Huge Exponents
Date: Tue, 16 Apr 2024 12:24:21 +0300
Organization: A noiseless patient Spider
Lines: 16
Message-ID: <871q757j96.fsf@fatphil.org>
References: <b1fbf007d052918737b3ad5b1987fa27$1@sybershock.com>
MIME-Version: 1.0
Content-Type: text/plain
Injection-Date: Tue, 16 Apr 2024 11:24:21 +0200 (CEST)
Injection-Info: dont-email.me; posting-host="f15427b9add8b35cb29e5b964a2d25b1";
logging-data="926848"; mail-complaints-to="abuse@eternal-september.org"; posting-account="U2FsdGVkX19GOWD2bORTGZi271OhY6yV"
User-Agent: Gnus/5.13 (Gnus v5.13) Emacs/26.1 (gnu/linux)
Cancel-Lock: sha1:JzcvXUI+HYIvqMN5xzLBSqaItek=
sha1:u9XbxdhvnIUxinRsbizXw6Q2Vno=
View all headers

SugarBug <3883@sugar.bug> 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/

1

rocksolid light 0.9.8
clearnet tor