summaryrefslogtreecommitdiffstats
diff options
context:
space:
mode:
authorjonsykkel <jonrevold@gmail.com>2021-09-20 18:02:31 +0200
committerjonsykkel <jonrevold@gmail.com>2021-09-20 18:02:31 +0200
commit6443416a5e2544cc605770657d986cd6c749a0e8 (patch)
tree034ea4231143bdd4a88da53f328c224e554a81e4
parent50d1ad7483665bcfa1859e48272a34038986cf1e (diff)
downloadokeffa-6443416a5e2544cc605770657d986cd6c749a0e8.tar.gz
mod exp
-rw-r--r--calc/main.c8
-rw-r--r--inc/okeffa/fz_arith.h1
-rw-r--r--src/fz_mod.c20
3 files changed, 29 insertions, 0 deletions
diff --git a/calc/main.c b/calc/main.c
index 4c64e3f..f7f904e 100644
--- a/calc/main.c
+++ b/calc/main.c
@@ -236,6 +236,14 @@ static void op_normal(char c){
drop();
break;
+ case 'X': //modular exponent
+ want(3);
+ mustnotzero(STACK(sp));
+ fz_mod_exp(STACK(sp-2),STACK(sp-1),STACK(sp),STACK(sp-2),fl);
+ drop();
+ drop();
+ break;
+
////////////////////////////////////////////////////////////////
//bitwise ops
////////////////////////////////////////////////////////////////
diff --git a/inc/okeffa/fz_arith.h b/inc/okeffa/fz_arith.h
index b5f5d88..ef09b4c 100644
--- a/inc/okeffa/fz_arith.h
+++ b/inc/okeffa/fz_arith.h
@@ -14,5 +14,6 @@ void fz_div (word_t *a,word_t *b,word_t *q,size_t len);
void fz_mod (word_t *a,word_t *b,word_t *r,size_t len);
void fz_mod_mul (word_t *a,word_t *b,word_t *m,word_t *o,size_t len);
+void fz_mod_exp (word_t *b,word_t *e,word_t *m,word_t *o,size_t len);
#endif
diff --git a/src/fz_mod.c b/src/fz_mod.c
index 7fa6e30..d70fc5b 100644
--- a/src/fz_mod.c
+++ b/src/fz_mod.c
@@ -1,5 +1,7 @@
#include <okeffa/fz_arith.h>
#include <okeffa/fz_basic.h>
+#include <okeffa/fz_shift.h>
+#include <okeffa/fz_pred.h>
void fz_mod_mul(word_t *a,word_t *b,word_t *m,word_t *o,size_t len){
size_t len2 = len*2;
@@ -15,3 +17,21 @@ void fz_mod_mul(word_t *a,word_t *b,word_t *m,word_t *o,size_t len){
fz_copy(xy_lo,o,len);
}
+void fz_mod_exp(word_t *_b,word_t *_e,word_t *m,word_t *o,size_t len){
+ size_t bitness = fz_bitness(len);
+ word_t b[len];
+ word_t e[len];
+ word_t t[len];
+
+ fz_copy(_b,b,len);
+ fz_copy(_e,e,len);
+ fz_frombool(o,len,1);
+
+ for(size_t x = 0;x < bitness;x++){
+ fz_mod_mul(o,b,m,t,len);
+ fz_mux(o,t,o,len,fz_odd(e));
+ fz_shr(e,e,len,1);
+ fz_mod_mul(b,b,m,b,len);
+ }
+}
+