Blog literacki, portal erotyczny - seks i humor nie z tej ziemi
/*
Author: Pate Williams (c) 1997
Fixed-base comb method for exponentiation. See
"Handbook of Applied Cryptography" by Alfred J.
Menezes et al 14.6.3 Section pages 623 - 627.
*/
#include
#include
#include
#include
#include "lip.h"
/*#define DEBUG*/
long binary_to_long(long t, long *e)
{
long i, value = e[t - 1];
for (i = t - 2; i >= 0; i--)
value = (value << 1) + e[i];
return value;
}
void long_to_binary(long a, long *e, long *t)
{
long i;
*t = z2logs(a);
for (i = 0; i < *t; i++) {
e[i] = a & 1;
a >>= 1;
}
}
void fixed_base_comb(long exp, verylong zg, verylong *zA)
{
long **EA, *X, *Y, Ijk, a, ah, b, c, e[32], f[32];
long h, h2, i, j, k, s, t, v;
verylong za = 0, zb = 0, zc = 0, **zG, *zg1;
long_to_binary(exp, e, &t);
t--;
do h = rand() % (t + 2); while (h == 0);
a = ceil((double)(t + 1) / h);
h2 = pow(2, h);
do v = rand() % (a + 1); while (v == 0);
b = ceil((double) a / v);
ah = a * h;
/* create the exponent array */
EA = calloc(h, sizeof(long *));
assert(EA != 0);
for (i = 0; i < h; i++) {
EA[i] = calloc(a, sizeof(long));
assert(EA[i] != 0);
}
/* allocate other arrays */
X = calloc(ah, sizeof(long));
assert(X != 0);
Y = calloc(h, sizeof(long));
assert(Y != 0);
zG = calloc(v, sizeof(verylong *));
assert(zG != 0);
for (j = 0; j < v; j++) {
zG[j] = calloc(h2, sizeof(verylong));
assert(zG[j] != 0);
}
zg1 = calloc(h, sizeof(zg1));
assert(zg1 != 0);
for (i = 0; i <= t; i++) X[i] = e[i];
/* create exponent array from binary representation */
i = 0;
for (j = 0; j < h; j++)
for (k = 0; k < a; k++)
EA[j][k] = X[i++];
for (i = 0; i < h; i++)
zsexp(zg, pow(2, i * a), &zg1[i]);
for (i = 1; i < h2; i++) {
long_to_binary(i, f, &s);
zone(&za);
for (j = 0; j < s; j++) {
zsexp(zg1[j], f[j], &zb);
zmul(zb, za, &zc);
zcopy(zc, &za);
}
zcopy(za, &zG[0][i]);
for (j = 1; j < v; j++)
zsexp(zG[0][i], pow(2, j * b), &zG[j][i]);
}
#ifdef DEBUG
printf("a = %ld\n", a);
printf("b = %ld\n", b);
printf("h = %ld\n", h);
printf("t = %ld\n", t + 2);
printf("v = %ld\n", v);
for (i = 0; i < h; i++) {
for (j = 0; j < a; j++)
printf("%d", EA[i][j]);
printf("\n");
}
printf("i g\n");
for (i = 0; i < h; i++) {
printf("%ld ", i);
zwriteln(zg1[i]);
}
printf("j i G[j][i]\n");
for (j = 0; j < v; j++) {
for (i = 1; i < h2; i++) {
printf("%ld %ld ", j, i);
zwriteln(zG[j][i]);
}
}
#endif
zone(zA);
for (k = b - 1; k >= 0; k--) {
zsq(*zA, &za);
zcopy(za, zA);
for (j = v - 1; j >= 0; j--) {
c = j * b + k;
for (i = 0; i < h; i++)
Y[i] = EA[i][c];
Ijk = binary_to_long(h, Y);
#ifdef DEBUG
printf("%ld %ld\n", j, Ijk);
#endif
if (Ijk != 0) {
zmul(*zA, zG[j][Ijk], &za);
zcopy(za, zA);
}
}
}
/* free the allocated resources */
free(X);
free(Y);
free(zg1);
for (i = 0; i < h; i++) free(EA[i]);
for (i = 0; i < v; i++) free(zG[i]);
zfree(&za);
zfree(&zb);
zfree(&zc);
}
void main(void)
{
long exp;
verylong zA = 0, za = 0, zg = 0;
srand(time(NULL));
zintoz(2l, &zg);
for (exp = 50l; exp < 155l; exp++) {
fixed_base_comb(exp, zg, &zA);
zsexp(zg, exp, &za);
/*zwriteln(zA);
zwriteln(za);*/
if (zcompare(zA, za) != 0)
printf("%ld error in exponent!\n", exp);
}
}