// Crafted @ May 5, 2018 By Babak Sheykhan #include #include #include #include #include #include #include #include #include /*-----------------------------*/ /* */ /* Conditional Compilation */ /* Block */ /* */ /*-----------------------------*/ // implementation dependant headers for Intel intrinsics #if defined(_MSC_VER) /* Microsoft C/C++-compatible compiler */ #include #elif defined(__GNUC__) || defined(__GNUG__) || defined(__clang__) #include /* GCC/G++/Clang-compatible compiler */ #endif using namespace std; mt19937 randGen(static_cast(time(NULL))); /* .................................... ... ____________________________ ... ...| Math (UML) |... ...+----------------------------+... ...| [No Attribute] |... ...|____________________________|... ...| [+] iPow64(UInt64, UInt64) |... ...| : UInt64 <> |... ...| [+] invSqrt(UInt64) |... ...| : Float <> |... ...| [+] nextPow2(UInt64) |... ...| : UInt64 <> |... ...| [-] iLog2(Double, Boolean) |... ...| : UInt64 <> |... ...| [-] sseSqrt(Float *) <> |... ...| [-] checkOverflow(UInt64, |... ...| UInt64) : Boolean <>|... ...|____________________________|... .................................... */ /*-----------------------------*/ /* */ /* Math.h */ /* */ /*-----------------------------*/ class Math { public: static uint_fast64_t iPow64(uint_fast64_t, uint_fast64_t); static float invSqrt(uint_fast64_t); static uint_fast64_t nextPow2(uint_fast64_t); private: static uint_fast64_t iLog2(double, bool); static void sseSqrt(float *); static bool checkOverflow(uint_fast64_t, uint_fast64_t); }; /*-----------------------------*/ /* */ /* Math.cpp */ /* */ /*-----------------------------*/ uint_fast64_t Math::iPow64(uint_fast64_t _base, uint_fast64_t _exp) { // Stand-alone version with description @ https://code.sololearn.com/cEo9hzjtccQ0 uint_fast64_t result = 0; if (_base == 0 && _exp == 0) { cout << "\nMath ERROR\n"; return result; } if (_base == 0) return result; if (_exp == 0) return ++result; if (checkOverflow(_base, _exp)) { cout << "\nWARNING: Arithmetic overflow on iPow64.\n"; return result; } // Make lists of power and the value to that power unsigned size = static_cast(nextPow2(_exp)); vector powers; powers.reserve(size); vector val2pow; val2pow.reserve(size); // Start with the power 1 and value^1 uint_fast64_t lastPow = 1; uint_fast64_t lastVal = _base; while (lastPow <= _exp) { powers.push_back(lastPow); val2pow.push_back(lastVal); lastPow <<= 1; lastVal *= lastVal; } result = 1; // Get the index of the largest power that is smaller than exponent. for (unsigned powIdx = powers.size() - 1; /*powIdx >= 0 &&*/ powIdx < powers.size(); --powIdx) { // See if this power fits within exponent. if (powers[powIdx] <= _exp) { _exp -= powers[powIdx]; result *= val2pow[powIdx]; } } return result; } float Math::invSqrt(uint_fast64_t _n) { if (_n == 0) return static_cast(_n); float f_n = static_cast(_n); sseSqrt(&f_n); return f_n; } uint_fast64_t Math::nextPow2(uint_fast64_t _n) { // Due to rounding Err of FP when the input is close to (2^64 - 1), I provided a safety check here. if (_n > 0xFFFFFFFFFFFFF9B0ULL) return 64U; bool isPowOf2 = ((_n - 1) & _n) == 0; return iLog2(static_cast(_n), isPowOf2); } uint_fast64_t Math::iLog2(double _n, bool isPowOf2) { if (_n == 0) { //cout << "\nMath ERROR\n"; return 0; } // Credit: http://stereopsis.com/log2.html uint_fast64_t sequence = 0; memcpy(&sequence, &_n, sizeof(sequence)); // portable compared to reinterpret_cast // IEEE 754 - Double precision // https://en.wikipedia.org/wiki/IEEE_754-1985 // // * Significant precision -> 52-bit (explicitly) // Shifting the floating point number to right by 52 bits elliminates the fraction part of the sequence. // // * Exponent field -> 11-bit // * 11-bit mask as hex number 0x7FF --Bin-> 0111 1111 1111 // * bias -> 1023 // After Shifting, what remains is 11 bits of exponent field. ANDing that with 0x7FF mask extracts the actual exponent bits. // Subtracting from bias yields the lovely log2 without a hassle :) uint_fast64_t exp = (sequence >> 52ULL) & 0x7FFULL; uint_fast64_t log2 = exp - 1023; // If iLog2 being called by nextPow2 function, check 2^x < _n < 2^x+1 then add 1 to log2 (round up to next higher power of 2), otherwise, round down to the lower power of 2. return log2 + (!isPowOf2); // is Eq. to "isPowOf2 ? log2 : log2 + 1;" but without branching } void Math::sseSqrt(float *_n) { __m128 tmp = _mm_load_ss(_n); _mm_store_ss(_n, _mm_mul_ss(tmp, _mm_rsqrt_ss(tmp))); } bool Math::checkOverflow(uint_fast64_t _base, uint_fast64_t _exp) { bool is_of = false; if (_base <= 0xFFFFULL && _base > 0x1ULL) { // Experimental Over-flow checker plot: https://ggbm.at/yCBWReFu const double A = 44.3572915; // For rough adjustment const double B = 0.0004218; // For fine adjustment unsigned max_exp = static_cast(A / log((double)_base) + B); if (_exp > max_exp) is_of = true; } else { if (_base <= 2642245 && _exp > 0x3ULL) is_of = true; else if (_base <= 0xFFFFFFFFULL && _exp > 0x2ULL) is_of = true; else if (_exp > 0x1ULL) is_of = true; } return is_of; } /* .................................... ... ____________________________ ... ...| Fast64_t (UML) |... ...+----------------------------+... ...| [-] result : UInt64 <> |... ...|____________________________|... ...| [+] toFastInt(String &) |... ...| : UInt64 <> |... ...| [-] checkValidity(String &)|... ...| : Boolean <>|... ...| [-] toString(UInt64) |... ...| : String <> |... ...| [-] toIntegral(String &) |... ...| : UInt64 <> |... ...| [-] getResult() |... ...| : UInt64 <> |... ...| [-] setResult(UInt64) <>|... ...|____________________________|... .................................... */ /*-----------------------------*/ /* */ /* Fast64_t.h */ /* */ /*-----------------------------*/ class Fast64_t { public: static uint_fast64_t toFastInt(uint_fast64_t); private: // Error tolerable validator static bool checkValidity(const string &); // Converters static string toString(uint_fast64_t); static uint_fast64_t toIntegral(const string &); static uint_fast64_t getResult(); static void setResult(uint_fast64_t); static uint_fast64_t result; }; /*-----------------------------*/ /* */ /* Fast64_t.cpp */ /* */ /*-----------------------------*/ uint_fast64_t Fast64_t::result; uint_fast64_t Fast64_t::toFastInt(uint_fast64_t in) { string s = toString(in); if (!checkValidity(s)) return NULL; return getResult(); } bool Fast64_t::checkValidity(const string &s) { string modifiable_input; bool isValid = true; // Visual debugging of the pattern : https://www.debuggex.com/r/XSa25c9KyeczK5jx // Range : [0 to 99,999,999,999,999,999,999] without upper-bound checking regex valid("\\+?\\b([1-9]\\d{0,19})\\b|0"); // Visual debugging of the pattern : https://www.debuggex.com/r/bQa4O6hEXQkxczL5 // Floating-point (rough) pattern regex fp("(\\+|-)?\\d+\\.\\d+"); // this one is not correctable -> (\\+|-)?\\d*\\.\\d+ // Range : [-9,999,999,999,999,999,999 to -1] regex neg("-\\b([1-9]\\d{0,18})\\b"); // Visual debugging of the pattern : https://www.debuggex.com/r/0b0NsKOeTEc14j8z regex tooLong("\\+?[1-9]\\d{20,100}|-[1-9]\\d{19,100}"); // Visual debugging of the pattern : https://www.debuggex.com/r/YmE8QnQUmZLiIaAb // Exact range : [0 to 18,446,744,073,709,551,615] regex exactRange("\\+?\\b((0|[1-9][0-9]{0,18})|1[0-7][0-9]{18}|18[0-3][0-9]{17}|184[0-3][0-9]{16}|1844[0-5][0-9]{15}|18446[0-6][0-9]{14}|184467[0-3][0-9]{13}|1844674[0-3][0-9]{12}|18446744[0][0-6][0-9]{10}|1844674407[0-2][0-9]{9}|18446744073[0-6][0-9]{8}|184467440737[0][0-8][0-9]{6}|18446744073709[0-4][0-9]{5}|184467440737095[0-4][0-9]{4}|1844674407370955[0][0-9]{3}|18446744073709551[0-5][0-9]{2}|184467440737095516[0][0-9]|1844674407370955161[0-5])\\b"); // Process invalid input and see whether it can be resolved or not. if (!regex_match(s, valid)) { cout << "WARNING : Invalid input. Trying to correct...\n"; modifiable_input = s; if (regex_match(s, fp)) { cout << "CODE 01 : FP input detected.\n"; // Handling negative FP regex fp_neg("-\\d+\\.\\d+"); if (regex_match(modifiable_input, fp_neg)) modifiable_input.erase(0, 1); // Handling long FP if (modifiable_input.length() > 20) modifiable_input.resize(20); setResult(toIntegral(modifiable_input)); cout << s << " has truncated to " << getResult() << endl; } else if (regex_match(s, neg)) { cout << "CODE 02 : Negative input detected.\n"; modifiable_input.erase(0, 1); setResult(toIntegral(modifiable_input)); cout << s << " has changed to " << getResult() << endl; } else if (regex_match(s, tooLong)){ cout << "CODE 03 : Too long number. Can't be resolved due to data loss.\n"; isValid = false; } else { cout << "CODE 04 : Undefined input. Can't be resolved.\n"; isValid = false; } } // Process upper bound validity if everything was a go at first glance. else if (!regex_match(s, exactRange)) { cout << "CODE 05 : Out of range. Terminating due to wrap around.\n"; isValid = false; } // Go for a clean conversion and get the result. else setResult(toIntegral(s)); return isValid; } string Fast64_t::toString(uint_fast64_t i) { stringstream num2str; num2str << i; return num2str.str(); } uint_fast64_t Fast64_t::toIntegral(const string &s) { uint_fast64_t numerical; stringstream str2num; str2num.str(s); str2num >> numerical; return numerical; } uint_fast64_t Fast64_t::getResult() { return result; } void Fast64_t::setResult(uint_fast64_t r) { result = r; } /* .................................... ... ____________________________ ... ...| PrimeToolkit (UML) |... ...+----------------------------+... ...| [-] primes_pool : |... ...| Vector <> |... ...| [+] MAX_RANGE : UShort = |... ...| 4096 <> |... ...|____________________________|... ...| [+] findPrimeFactors |... ...| (UInt64) <> |... ...| [+] getRandomPrime(UInt64) |... ...| <> |... ...| [+] makePublicKey() <> |... ...| [-] populatePrimes(UInt64&)|... ...| <> |... ...|____________________________|... .................................... */ /*-----------------------------*/ /* */ /* PrimeToolkit.h */ /* */ /*-----------------------------*/ class PrimeToolkit { public: static void findPrimeFactors(uint_fast64_t); static void getRandomPrime(uint_fast64_t); // Credit : https://stackoverflow.com/questions/439870/why-are-primes-important-in-cryptography // Multiplying two large prime numbers, yields a huge non-prime number with only two large prime factors. // The product of the two prime numbers can be used as a public key, while the primes themselves as a private key. // Side Note : Personally, I'm not terribly interested in cryptography, but it'd be lame if I ignore it completely. Someday, somebody might ask me about that and as a matter of fact I stumbling over a simple explanation; Then all of sudden a nagging sound from the back of my mind will tell me : "You idiot! why didin't you learn that crap the other day, hah??". RIGHT!...DICK! static void makePublicKey(); // Instead of implementing Fermat's little theorem (A probabilistic algorithm) which needs Big Integer library to operate, I prefered modify findPrimeFactors() to determine primality confidently. // https://en.wikipedia.org/wiki/Fermat%27s_little_theorem //static void testPrimality(uint_fast64_t); static const unsigned short MAX_RANGE = 4096; private: // Using Sieve of Eratosthenes Algorithm (limited range) // https://en.wikipedia.org/wiki/Sieve_of_Eratosthenes static void populatePrimes(uint_fast64_t &); static vector primes_pool; }; /*-----------------------------*/ /* */ /* PrimeToolkit.cpp */ /* */ /*-----------------------------*/ vector PrimeToolkit::primes_pool; void PrimeToolkit::findPrimeFactors(uint_fast64_t num) { uint_fast64_t n = num; vector factors; factors.reserve(static_cast(Math::nextPow2(num))); cout << "Prime factor(s) of " << num << " is/are: "; // Pull out factors of 2 while (num % 2 == 0) { // Or !(num & 0x1ULL) factors.push_back(2); num /= 2; // Or num >>= 1 } // Look for odd factors uint_fast64_t odd_factor = 3; unsigned stop_at = static_cast(Math::invSqrt(num)); while (odd_factor <= stop_at) { // Pull out this factor while (num % odd_factor == 0) { factors.push_back(odd_factor); num /= odd_factor; // Set a new upper bound stop_at = static_cast(Math::invSqrt(num)); } // Check next possible odd factor odd_factor += 2; } // If there's anything left of the num, it's a factor, too. if (num > 1) factors.push_back(num); /*for (const auto &i : outcome) cout << i << " ";*/ for (size_t i = 0; i < factors.size(); ++i) cout << factors[i] << " "; if (factors.size() == 2) cout << endl << n << " can be chosen as a public key."; // If the number itself is the only factor, then it's prime. cout << endl << n << " is " << (factors.size() == 1 ? "prime\n\n" : "NOT prime\n\n"); } void PrimeToolkit::getRandomPrime(uint_fast64_t range) { //cout << "\nPool size before : " << primes_pool.size() << endl; //cout << "Pool capacity before : " << primes_pool.capacity() << endl << endl; if (primes_pool.size()) { primes_pool.clear(); primes_pool.shrink_to_fit(); } //cout << "Pool size after : " << primes_pool.size() << endl; //cout << "Pool capacity after : " << primes_pool.capacity() << endl << endl; cout << "\nPopulating primes in the range [2, " << range << "]...\n"; populatePrimes(range); cout << "Selecting random prime in the range [2, " << range << "]...\n"; uniform_int_distribution dist(0, primes_pool.size()-1); cout << "Selected prime is : " << primes_pool[dist(randGen)] << endl; } void PrimeToolkit::makePublicKey() { if (primes_pool.size()) { primes_pool.clear(); primes_pool.shrink_to_fit(); } uint_fast64_t max = MAX_RANGE; cout << "\nPopulating primes in the range [2, " << max << "]...\n"; populatePrimes(max); uniform_int_distribution dist(0, primes_pool.size()-1); uint_fast64_t p1 = primes_pool[dist(randGen)]; uint_fast64_t p2 = primes_pool[dist(randGen)]; uint_fast64_t p_key = p1 * p2; cout << "Random public key is : " << p_key << endl; findPrimeFactors(p_key); } void PrimeToolkit::populatePrimes(uint_fast64_t &upTo) { if (upTo > 4096 || upTo < 2) { cout << "\nOut of range. Input range must be [2, 4096]\n"; uniform_int_distribution dist(2, MAX_RANGE); upTo = dist(randGen); cout << "Max range being randomely chosen to : " << upTo << endl; } //cout << "Prime list up to " << upTo << ":\n"; primes_pool.reserve(MAX_RANGE >> 2); vector is_prime(static_cast(upTo+1), true); is_prime[0] = false; is_prime[1] = false; // 1 isn't prime // Cross out multiples of 2 for (int i = 4; i <= upTo; i += 2) is_prime[i] = false; unsigned next_prime = 3; unsigned stop_at = static_cast(Math::invSqrt(upTo)); while (next_prime <= stop_at) { if (is_prime[next_prime]) for (unsigned i = next_prime * next_prime; i <= upTo; i += 2 * next_prime) is_prime[i] = false; ++next_prime; } unsigned count = 0; for (size_t i = 1; i < is_prime.size(); ++i) if (is_prime[i]) { ++count; primes_pool.push_back(i); //cout << i << "\n"; } cout << "Total populated primes : " << count << endl << endl; } /*-----------------------------*/ /* */ /* Client */ /* */ /*-----------------------------*/ int main() { cout << "/*-----------------------------*/\n"; cout << "/* */\n"; cout << "/* DEMO */\n"; cout << "/* */\n"; cout << "/*-----------------------------*/\n\n"; uniform_int_distribution dist(0, PrimeToolkit::MAX_RANGE << 1 /*Doubled max range*/); uint_fast64_t input = Fast64_t::toFastInt(dist(randGen)); cout << "/*-----------------------------*/\n"; cout << "/* Finding Prime Factors */\n"; cout << "/*-----------------------------*/\n"; PrimeToolkit::findPrimeFactors(input); cout << "/*-----------------------------*/\n"; cout << "/* Get Random Primes x3 */\n"; cout << "/*-----------------------------*/"; PrimeToolkit::getRandomPrime(input); PrimeToolkit::getRandomPrime(input); PrimeToolkit::getRandomPrime(input); cout << "\n/*-----------------------------*/\n"; cout << "/* Make a Public Key */\n"; cout << "/*-----------------------------*/"; PrimeToolkit::makePublicKey(); } /* Ref links: https://stackoverflow.com/questions/439870/why-are-primes-important-in-cryptography https://en.wikipedia.org/wiki/Fermat%27s_little_theorem https://en.wikipedia.org/wiki/Sieve_of_Eratosthenes */

Simple prime toolkit