Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]
Groups > comp.lang.forth > #57516
| From | "David N. Williams" <williams@umich.edu> |
|---|---|
| Newsgroups | comp.lang.forth |
| Subject | Re: string-stack.4th |
| Date | 2017-04-17 20:11 -0500 |
| Organization | University of Michigan |
| Message-ID | <od3our$6pv$1@dont-email.me> (permalink) |
| References | (3 earlier) <4bce5098-0505-41b7-8bf6-4263846d3bb2@googlegroups.com> <41c816a2-6258-4e2d-8693-2cf2a7cd8d6c@googlegroups.com> <562e4faf-9de1-4f9e-b0b2-ef25e97f222b@googlegroups.com> <3db60aeb-6eb3-4445-bef2-7fd241c8b89c@googlegroups.com> <87tw5no388.fsf@nightsong.com> |
On 4/17/17 3:19 AM, Paul Rubin wrote:
> lehs <skydda.barnen@gmail.com> writes:
>> I might be able to speed up my bigintegers.4th
>
> I wonder if you could run a test for me: let p = 17**250 + 2704
> (this number happens to be prime) and time how long it takes for
> your implementation to do a Fermat test: calculate (3**p) mod p
> which should be equal to 3.
>
> My feeling is that if this takes less than a few seconds, your package
> is reasonably usable for public-key cryptography.
Out of curiosity, I tried this with the integer part of my forth-gmpfr
package, which has a garbage collected bignum stack in ANS Forth, with
bindings to the GNU Multiple Precision library:
http://www.umich.edu/~williams/archive/forth/gmpfr/
I used pfe for the timings. In the file names 3^p_mod_p_xxx.fs below,
"xxx" indicates the number of trials. The trials were run on a MacBook
Pro 2.2 GHz Intel Core i7 (4 cores) under macOS Sierra 10.12.4. The
gmpfr package and GNU libraries used haven't been changed since January,
2012.
[haag:~/gmpfr] dnwills% /usr/bin/time -p pfe -q -y 3^p_mod_p_100.fs
real 0.32
user 0.31
sys 0.00
[haag:~/gmpfr] dnwills% /usr/bin/time -p pfe -q -y 3^p_mod_p_200.fs
real 0.70
user 0.69
sys 0.00
[haag:~/gmpfr] dnwills% /usr/bin/time -p pfe -q -y 3^p_mod_p_1000.fs
real 2.95
user 2.94
sys 0.00
So the user time for one calculation is less than 3 milliseconds. I
don't know how much of that is bignum stack overhead, compared to the
GNU library calls.
Here's the 1000-trial code:
3^p_mod_p_1000.fs
-----------------
\ Title: GMPFR Benchmark for (3**p) mod p with a large prime p
\ File: 3^p_mod_p_1000.fs
\ Author: David N. Williams
\ Date: April 17, 2017
\ License: public domain
\ To run with pfe:
\ /usr/bin/time -p pfe -q -y 3^p_mod_p_1000.fs
true constant MULTI-INTEGERS
s" gmpfr.fs" INCLUDED
17 u>b 250 b^u 2704 bu+ bconstant p
: tries ( n -- )
0 DO
3 u>b p p b-pow-mod \ 3^p mod p
bdrop
\ b.
LOOP
;
1000 tries
bye
-----------------
Here are some checks (long result broken into lines):
p b. 40947778423540104959067988292528857405972603447195632195037
8594747292053767136408255971273136413908600752651227962494772762
1804563995511385846512375859465262648854834054706258499178583491
6459459029262407818318245524277482110372262457010816382213629216
030118638993632313978231084140883786669390389605436763953 ok
3 u>b p p b-pow-mod b. 3 ok
I haven't tested whether the value of p above is correct, but at least
it's big, odd, and produces 3 in the calculation.
-- David W.
Back to comp.lang.forth | Previous | Next — Previous in thread | Next in thread | Find similar | Unroll thread
Re: string-stack.4th lehs <skydda.barnen@gmail.com> - 2017-04-16 08:23 -0700
Re: string-stack.4th lehs <skydda.barnen@gmail.com> - 2017-04-16 08:33 -0700
Re: string-stack.4th "Rudy Velthuis" <newsgroups@rvelthuis.de> - 2017-04-16 22:34 +0000
Re: string-stack.4th lehs <skydda.barnen@gmail.com> - 2017-04-16 17:11 -0700
Re: string-stack.4th "Rudy Velthuis" <newsgroups@rvelthuis.de> - 2017-04-17 23:22 +0000
Re: string-stack.4th lehs <skydda.barnen@gmail.com> - 2017-04-17 18:14 -0700
Re: string-stack.4th hughaguilar96@gmail.com - 2017-04-17 18:44 -0700
Re: string-stack.4th "Rudy Velthuis" <newsgroups@rvelthuis.de> - 2017-04-19 23:09 +0000
Re: string-stack.4th lehs <skydda.barnen@gmail.com> - 2017-04-16 09:02 -0700
Re: string-stack.4th lehs <skydda.barnen@gmail.com> - 2017-04-16 15:29 -0700
Re: string-stack.4th hughaguilar96@gmail.com - 2017-04-16 19:43 -0700
Re: string-stack.4th hughaguilar96@gmail.com - 2017-04-16 22:42 -0700
Re: string-stack.4th hughaguilar96@gmail.com - 2017-04-16 23:09 -0700
Re: string-stack.4th lehs <skydda.barnen@gmail.com> - 2017-04-16 23:34 -0700
Re: string-stack.4th lehs <skydda.barnen@gmail.com> - 2017-04-17 00:15 -0700
Re: string-stack.4th Paul Rubin <no.email@nospam.invalid> - 2017-04-17 01:19 -0700
Re: string-stack.4th lehs <skydda.barnen@gmail.com> - 2017-04-17 02:06 -0700
Re: string-stack.4th lehs <skydda.barnen@gmail.com> - 2017-04-17 02:50 -0700
Re: string-stack.4th Paul Rubin <no.email@nospam.invalid> - 2017-04-17 13:14 -0700
Re: string-stack.4th lehs <skydda.barnen@gmail.com> - 2017-04-17 15:58 -0700
Re: string-stack.4th Paul Rubin <no.email@nospam.invalid> - 2017-04-17 16:57 -0700
Re: string-stack.4th "Elizabeth D. Rather" <erather@forth.com> - 2017-04-17 15:07 -1000
Re: string-stack.4th lehs <skydda.barnen@gmail.com> - 2017-05-17 05:32 -0700
Re: string-stack.4th hughaguilar96@gmail.com - 2017-04-17 19:49 -0700
Re: string-stack.4th "David N. Williams" <williams@umich.edu> - 2017-04-17 20:11 -0500
Re: string-stack.4th Paul Rubin <no.email@nospam.invalid> - 2017-04-17 18:15 -0700
Re: string-stack.4th lehs <skydda.barnen@gmail.com> - 2017-04-17 19:13 -0700
Re: string-stack.4th Paul Rubin <no.email@nospam.invalid> - 2017-04-17 19:21 -0700
Re: string-stack.4th lehs <skydda.barnen@gmail.com> - 2017-04-18 01:25 -0700
Re: string-stack.4th Paul Rubin <no.email@nospam.invalid> - 2017-04-18 19:27 -0700
Re: string-stack.4th "David N. Williams" <williams@umich.edu> - 2017-04-18 11:27 -0500
Re: string-stack.4th mhx@iae.nl - 2017-04-18 11:53 -0700
Re: string-stack.4th albert@cherry.spenarnc.xs4all.nl (Albert van der Horst) - 2017-04-20 20:48 +0200
Re: string-stack.4th mhx@iae.nl - 2017-04-20 14:58 -0700
Re: string-stack.4th lehs <skydda.barnen@gmail.com> - 2017-04-17 00:46 -0700
Re: string-stack.4th hughaguilar96@gmail.com - 2017-04-16 19:31 -0700
csiph-web