Skip to content

Instantly share code, notes, and snippets.

@sasaki-shigeo
Created January 13, 2021 04:20
Show Gist options
  • Save sasaki-shigeo/02b62873aba9b94c02040212edf3afb3 to your computer and use it in GitHub Desktop.
Save sasaki-shigeo/02b62873aba9b94c02040212edf3afb3 to your computer and use it in GitHub Desktop.
#include <stdlib.h>
#include <stdio.h>
int gcd(int m, int n) {
int r = m % n;
if (r == 0) {
return n;
}
else {
return gcd(n, r);
}
}
long lgcd(long m, long n) {
long r = m % n;
if (r == 0) {
return n;
}
else {
return lgcd(n, r);
}
}
int lcm(int m, int n) {
return m / gcd(m, n) * n;
}
int llcm(long m, long n) {
return m / lgcd(m, n) * n;
}
const int p = 4327;
const int q = 60013;
const int n = p * q;
const int L = 43268652;
const int e = 65537;
const int d = 42152885;
int slow_powmod(int x, unsigned int k, int n) {
long y = 1L;
for (int i = 0; i < k; i++) {
y *= x;
y %= n;
}
return (int)y;
}
int fast_powmod(int x, unsigned int k, int n) {
if (k == 0) {
return 1L;
}
else if (k % 2 == 0) {
long y = fast_powmod(x, k/2, n);
return (int)(y * y % n);
}
else {
long y = fast_powmod(x, k - 1, n);
return (int)(x * y % n);
}
}
int fast_fast_powmod(int x, unsigned int k, int n) {
const unsigned int MSB = 1 << (8 * sizeof(int) - 1);
long y = 1L;
for (unsigned int bit = MSB; bit != 0; bit >>= 1) {
y = (y * y) % n;
if (bit & k) {
y = y * x % n;
}
}
return (int)y;
}
int powmod(int x, int k, int n) {
return fast_powmod(x, k, n);
}
int encrypt(int m) {
return powmod(m, e, n);
}
int decrypt(int c) {
return powmod(c, d, n);
}
int main() {
sranddev();
int m = rand() % n;
int c = encrypt(m);
int m2 = decrypt(c);
printf("original text = %d, encrypted text = %d, decrypted text = %d\n", m, c, m2);
exit(0);
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment