drazioti / carmichael Goto Github PK
View Code? Open in Web Editor NEWC++ code for finding Carmichael Numbers with many factors
License: GNU General Public License v2.0
C++ code for finding Carmichael Numbers with many factors
License: GNU General Public License v2.0
in the input parameters i.e. ./carmichael.out L --ham 20 -b 30 -q 10 -f 1
check that the elements of the set L = [a1,...,ar] are such that
a>=a2>=...>=ar
It seems that the parallel version does not work as expected (this can be seen experimentally).
Is link GMP error because is #include "subset_product.cpp" , I changed to #include "subset_product.h"
and it is:
#pragma once
#include <list>
#include <gmpxx.h>
void randomize_I(gmp_randclass &rr, unsigned int seed);
void gen_I(mpz_class &n, mpz_class &b, int flag, mpz_class** &I, gmp_randclass &rr, unsigned int seed);
void arrcpy(mpz_class* &dest, mpz_class* &source, mpz_class &size);
int product_attack_1(mpz_class* &P,mpz_class &sizeP, mpz_class &Lambda, mpz_class &c, mpz_class** &I,int local_hamming_weight,mpz_class &sizeI, std::list<int*> &sol1, std::list<int*> &sol2, mpz_class &count, int frag, double total_time, char Q_bytes);
#24 After the introduction of md5 hash in unordered map, we must add the parameter Q (where Q is the number of hex bytes we consider from the message digest).
Sometime if you consider a "large" instance e.g.
./a.out 35 25 15 10 1 1 1 1 1 1 1 1 --ham 15 -b 32 -f 1
this will immediately stored in the ram. Although sometimes the system hangs instead of killed.
I suppose that we wait until the swap memory overflow. One method to solve this, is
before the program start, to check (using the prediction function for P_set) and compare with the existing memory. If it occurs that |P_set|*r (bytes)> RAM the the program will stop.
After the algorithm terminates successfully, the carm_num.txt files is created, but it is empty.
This phenomenon occurs only in the parallel version.
#27 Please check the following for the parallel version
In every step I1,I2 are different?
In ever new execution of the program are I1,I2 different?
An argument that would let the user to run the program with a no randomization at all.
This would be helpful with the comparison of different strategies.
https://github.com/drazioti/python_scripts/blob/master/git_roadmap
Από την γραμμή 90 και μετά, μπορειτε να δειτε πως θα κάνετε sync το local fork που εχετε με το remote (το δικό μου).
(concerns #17 )
Executing for the single core case.
./a.out 45 10 4 1 1 --ham 15 -b 32 -f 1
Lambda is : 72610699640222177280000000000000000000
hamming : 15
P size is : 23436
looking for Carmichaels with 23421 factors
density of the problem : 189.757907
Size of I is : 32
h1 = 7
h2 = 8
frag = 1
Although the right value of Lambda prime factors is 2310 (see the sagemath code)
The parallel code is working fine for these values.
So comparing with the previous issue we conclude that for some small values the parallel does not compute a valid Lambda but the single core do.
On the contrary, when we use large values e.g. ./a.out 45 10 4 1 1 --ham 15 -b 32 -f 1, the parallel computes a valid value of Lambda. But the single core not.
(concerns #24 )
If you provide the following value.
[single core] ./a.out 100 39 38 1 1 --ham 15 -b 32 -f 1
you got :
looking for Carmichaels with 23421 factors
[multicore] ./a.out 100 39 38 1 1 --ham 15 -b 32 -f 1
you got :
looking for Carmichaels with 29744 factors
Although the right value is 32588
So both implementations compute the wrong number of factors.
./a.out 45 10 4 1 1 --ham 15 -b 32 -f 1
Lambda is : 72610699640222177280000000000000000000
hamming : 15
P size is : 23436
looking for Carmichaels with 23421 factors
./a.out 45 10 4 1 1 --ham 15 -b 32 -f 1
H values : 45 10 4 1 1
Bound : 32
Fragmentation : 1
Lambda is : 99984595647159336960000
hamming : 15
P size is : 1612
looking for Carmichaels with 1597 factors
density of the problem : 21.743430
EDIT1. The right value is (99984595647159336960000, [2, 3, 5, 7, 11])
[single core case] #24
./a.out 5 1 1 1 1 1 --ham 15 -b 20 -f 1
Lambda is : 99984595647159336960000
hamming : 15
P size is : 1612
looking for Carmichaels with 1597 factors
density of the problem : 21.743430
Size of I is : 32
h1 = 7
h2 = 8
frag = 1
The first set U1, has been stored in memory
Hashtable size : 3365856
Although the right value for lambda is 480480 and for the P size, 61.
(concerns #24 ) When I run
./a.out 40 39 38 1 1 --ham 15 -b 32 -f 1
I got the following
Bound : 32
Fragmentation : 1
Lambda is : 124818698712984465874893716083283958827305735281288532721664
hamming : 15
P size is : 15863
looking for Carmichaels with 15848 factors
density of the problem : 81.748318
Size of I is : 32
h1 = 7
h2 = 8
Hash Implementation: True
Combination time: 2.451523 seconds
frag = 1
Time for func2 is: 7.467367 seconds
The first set U1, has been stored in memory
Hashtable size : 3365856
Inverted is : Inverted is : Inverted is : Inverted is : 00
Number 102464604362751399936000000000000000001 doesnt have inverse modulo 124818698712984465874893716083283958827305735281288532721664
0
Why the hash table size is constant at 3365856?
The program continues until it founds a solution. In each step chooses new I1,I2, the problem is that as the rounds increasing the memory increases, so soon or later will have a memory overflow.
(I checked this in parallel)
Στον αλλον υπολογιστη εχω το εξης
$g++ --std=c++11 carmi.cpp Combinations.cpp -lgmpxx -lgmp -lcrypto -fopenmp
g++ --std=c++11 carmi.cpp Combinations.cpp -lgmpxx -lgmp -lcrypto -fopenmp
/tmp/ccKrur6S.o: In function divisors(int*, int*, int, __gmp_expr<__mpz_struct [1], __mpz_struct [1]>&, unsigned char**&)': carmi.cpp:(.text+0x46b): undefined reference to
mpz_2_ull(__gmp_expr<__mpz_struct [1], __mpz_struct [1]>)'
carmi.cpp:(.text+0x6b7): undefined reference to arrcpy(__gmp_expr<__mpz_struct [1], __mpz_struct [1]>*&, __gmp_expr<__mpz_struct [1], __mpz_struct [1]>*&, __gmp_expr<__mpz_struct [1], __mpz_struct [1]>&)' /tmp/ccKrur6S.o: In function
make_P_set(int*, int*, int, __gmp_expr<__mpz_struct [1], __mpz_struct [1]>&, std::list<unsigned char*, std::allocator<unsigned char*> >&)':
carmi.cpp:(.text+0xb26): undefined reference to mpz_2_ull(__gmp_expr<__mpz_struct [1], __mpz_struct [1]>)' /tmp/ccKrur6S.o: In function
T_set(int*, int, unsigned char**&, __gmp_expr<__mpz_struct [1], __mpz_struct [1]>&, __gmp_expr<__mpz_struct [1], __mpz_struct [1]>&, __gmp_expr<__mpz_struct [1], __mpz_struct [1]>&, __gmp_expr<__mpz_struct [1], __mpz_struct [1]>&, int, double, int, char)':
carmi.cpp:(.text+0xf55): undefined reference to get_P_element(int*&, unsigned char*&, int)' carmi.cpp:(.text+0x1088): undefined reference to
product_attack_1(int*&, int, unsigned char&, __gmp_expr<__mpz_struct [1], __mpz_struct [1]>&, __gmp_expr<__mpz_struct [1], __mpz_struct [1]>&, __gmp_expr<__mpz_struct [1], __mpz_struct [1]>&, __gmp_expr<__mpz_struct [1], __mpz_struct [1]>&, int, __gmp_expr<__mpz_struct [1], __mpz_struct [1]>&, std::list<int*, std::allocator<int*> >&, std::list<int*, std::allocator<int*> >&, __gmp_expr<__mpz_struct [1], __mpz_struct [1]>&, double, int, char)'
/tmp/ccKrur6S.o: In function extract_number(__gmp_expr<__mpz_struct [1], __mpz_struct [1]>*&, __gmp_expr<__mpz_struct [1], __mpz_struct [1]>**&, __gmp_expr<__mpz_struct [1], __mpz_struct [1]>&, std::list<int*, std::allocator<int*> >&, std::list<int*, std::allocator<int*> >&, int, int, __gmp_expr<__mpz_struct [1], __mpz_struct [1]>*&)': carmi.cpp:(.text+0x1844): undefined reference to
is_carmichael(__gmp_expr<__mpz_struct [1], __mpz_struct [1]>&, __gmp_expr<__mpz_struct [1], __mpz_struct [1]>*&, __gmp_expr<__mpz_struct [1], __mpz_struct [1]>&)'
/tmp/ccKrur6S.o: In function main': carmi.cpp:(.text+0x2ff3): undefined reference to
randomize_I(gmp_randclass&, unsigned int)'
carmi.cpp:(.text+0x3152): undefined reference to `gen_I(__gmp_expr<__mpz_struct [1], __mpz_struct [1]>&, __gmp_expr<__mpz_struct [1], __mpz_struct [1]>&, int, __gmp_expr<__mpz_struct [1], __mpz_struct [1]>&, gmp_randclass&, unsigned int)'
collect2: error: ld returned 1 exit status
Φυσικα αποτυγχανει και η make.
Eχει καταφερει να δημιουργησει τα object files.
Το Makefile δε νομιζω να εχει θέμα. Ίσως τα header files
A declarative, efficient, and flexible JavaScript library for building user interfaces.
🖖 Vue.js is a progressive, incrementally-adoptable JavaScript framework for building UI on the web.
TypeScript is a superset of JavaScript that compiles to clean JavaScript output.
An Open Source Machine Learning Framework for Everyone
The Web framework for perfectionists with deadlines.
A PHP framework for web artisans
Bring data to life with SVG, Canvas and HTML. 📊📈🎉
JavaScript (JS) is a lightweight interpreted programming language with first-class functions.
Some thing interesting about web. New door for the world.
A server is a program made to process requests and deliver data to clients.
Machine learning is a way of modeling and interpreting data that allows a piece of software to respond intelligently.
Some thing interesting about visualization, use data art
Some thing interesting about game, make everyone happy.
We are working to build community through open source technology. NB: members must have two-factor auth.
Open source projects and samples from Microsoft.
Google ❤️ Open Source for everyone.
Alibaba Open Source for everyone
Data-Driven Documents codes.
China tencent open source team.