0353547 ...
Das ist nicht ungewöhnlich, da (pi(10^22) - pi(10^21))/(10^22 - 10^21) immer noch relativ klein ist (pi(x) ist grob gleich x/log(x)). D.h. selbst bei so großen Zahlen ist, wenn ich mich nicht verrechnet habe, jede ca. 50te Zahl eine Primzahl. Diese läßt sich logischerweise in drei Siebener-Gruppen oder sieben Dreier-Gruppen "zerlegen" ...
Immer auch das Originalbild beachten, da sind vllt. Informationen versteckt (
). Da ist ein einziger schwarzer Pixel ausserhalb des Gesichts im rechten unteren Viertel des Bildes (man muss dazu etwas reinzoomen). Das ist bestimmte kein Zufall. Desweiteren scheint die 21 eine Rolle zu spielen (Annahme von mir).
Bye.
// gcc -Wall <file_name>.c -o <file_name> -lcrypto -std=c99
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#include <string.h>
#include <boost/multiprecision/cpp_int.hpp>
using namespace boost::multiprecision;
/*static char *qtoa(uint256_t n){
static char buf[80];
unsigned int i, j, m = 79;
memset(buf, 0, 80);
for (i = 256; i-- > 0;){
int carry = !!(n & ((uint256_t)1 << i));
for (j = 79; j-- > m + 1 || carry;){
int d = 2*buf[j] + carry;
carry = d > 9;
buf[j] = carry ? d - 10 : d;
}
m = j;
}
for (i = 0; i < 78; i++){
if (buf[i]){
break;
}
}
for (j = i; j < 79; j++){
buf[j] += '0';
}
return buf + i;
}*/
// calcul a^n%mod
uint256_t power(uint256_t a, uint256_t n, uint256_t mod)
{
uint256_t power = a;
uint256_t result = 1;
while (n)
{
if (n & 1)
result = (result * power) % mod;
power = (power * power) % mod;
n >>= 1;
}
return result;
}
// n−1 = 2^s * d with d odd by factoring powers of 2 from n−1
bool witness(uint256_t n, uint256_t s, uint256_t d, uint256_t a)
{
uint256_t x = power(a, d, n);
uint256_t y;
while (s) {
y = (x * x) % n;
if (y == 1 && x != 1 && x != n-1)
return false;
x = y;
--s;
}
if (y != 1)
return false;
return true;
}
/*
* if n < 1,373,653, it is enough to test a = 2 and 3;
* if n < 9,080,191, it is enough to test a = 31 and 73;
* if n < 4,759,123,141, it is enough to test a = 2, 7, and 61;
* if n < 1,122,004,669,633, it is enough to test a = 2, 13, 23, and 1662803;
* if n < 2,152,302,898,747, it is enough to test a = 2, 3, 5, 7, and 11;
* if n < 3,474,749,660,383, it is enough to test a = 2, 3, 5, 7, 11, and 13;
* if n < 341,550,071,728,321, it is enough to test a = 2, 3, 5, 7, 11, 13, and 17;
* if n < 318,665,857,834,031,151,167,461, it is enough to test a = 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37.
*/
bool is_prime_mr(uint256_t n)
{
if (((!(n & 1)) && n != 2 ) || (n < 2) || (n % 3 == 0 && n != 3))
return false;
if (n <= 3)
return true;
uint256_t d = n / 2;
uint256_t s = 1;
while (!(d & 1)) {
d /= 2;
++s;
}
if (n < 1373653)
return witness(n, s, d, 2) && witness(n, s, d, 3);
if (n < 9080191)
return witness(n, s, d, 31) && witness(n, s, d, 73);
if (n < 4759123141)
return witness(n, s, d, 2) && witness(n, s, d, 7) && witness(n, s, d, 61);
if (n < 1122004669633)
return witness(n, s, d, 2) && witness(n, s, d, 13) && witness(n, s, d, 23) && witness(n, s, d, 1662803);
if (n < 2152302898747)
return witness(n, s, d, 2) && witness(n, s, d, 3) && witness(n, s, d, 5) && witness(n, s, d, 7) && witness(n, s, d, 11);
if (n < 3474749660383)
return witness(n, s, d, 2) && witness(n, s, d, 3) && witness(n, s, d, 5) && witness(n, s, d, 7) && witness(n, s, d, 11) && witness(n, s, d, 13);
if (n < 341550071728321)
return witness(n, s, d, 2) && witness(n, s, d, 3) && witness(n, s, d, 5) && witness(n, s, d, 7) && witness(n, s, d, 11) && witness(n, s, d, 13) && witness(n, s, d, 17);
return witness(n, s, d, 2) && witness(n, s, d, 3) && witness(n, s, d, 5) && witness(n, s, d, 7) && witness(n, s, d, 11) && witness(n, s, d, 13) && witness(n, s, d, 17) && witness(n, s, d, 19) && witness(n, s, d, 23) && witness(n, s, d, 29) && witness(n, s, d,
31) && witness(n, s, d, 37);
}
void padstring(char hexstring[], char *buf){
int l = strlen(hexstring);
for (int i = 0; i < 64 - l; i++)
buf[i] = '0';
for (int i = 0; i < l; i++)
buf[64 - l + i] = hexstring[i];
}
uint256_t string2int256(char hexstring[]){
unsigned char val[32];
for (int i = 0; i < 32; i++)
sscanf(&hexstring[2*i], "%2hhx", &val[i]);
uint256_t ret = 0;
for (int i = 0; i < 32; i++){
ret = ret << 8;
ret = ret | val[i];
}
return ret;
}
int main(int argc, char *argv[]){
char buf[128] = {0};
padstring(argv[1], buf);
uint256_t x = string2int256(buf);
printf("%d\n", is_prime_mr(x));
return 0;
}
ergibt 1.
