Revision history [back]

The function log of Finite rings calls directly the function znlog of Pari. According to the documentation, znlog uses first the Pohlig-Hellman algorithm, to reduce to groups of prime order. Then it uses a a linear sieve index calculus method. For a faster (and parallel) implementation, you may use CADO-NFS but it will solve the discrete log only in one subgroup each time:

$ ./cado-nfs.py -dlp -ell 1536021852403835577250850726481014637179 target=82936225177577666415052331393239668755262693348731690326562114609848154162166 13579208921035624875642034521402089276606162372495774456784380935629343904605

...

Info:Log queries: Checking that log(3)=1404106513053697738808612862784757866144 is correct in base 7785272685885784582564928906403856210181547208520333383076510590456824439275...
Info:Log queries: Checking that log(3)=1404106513053697738808612862784757866144 is correct in base 7785272685885784582564928906403856210181547208520333383076510590456824439275... passed

...

Info:root: logbase = 7785272685885784582564928906403856210181547208520333383076510590456824439275
Info:root: target = 82936225177577666415052331393239668755262693348731690326562114609848154162166
Info:root: log(target) = 712407062525843960939316924588302612885 mod ell
712407062525843960939316924588302612885

Hopefully in your case is is sufficent to solve in in the largest subgroup since the exponent is small:

sage: ell=1536021852403835577250850726481014637179
sage: inverse_mod(1404106513053697738808612862784757866144,ell)*712407062525843960939316924588302612885 % ell
212223489

You would have finished the Pohlig-Hellman algorithm for larger exponent values.

The function log of Finite rings calls directly the function znlog of Pari. According to the documentation, znlog uses first the Pohlig-Hellman algorithm, to reduce to groups of prime order. Then it uses a a linear sieve index calculus method. For a faster (and parallel) implementation, you may use CADO-NFS but it will solve the discrete log only in one subgroup each time:time. So first you have to factorize p-1:

sage: factor(b.multiplicative_order())
2 * 3 * 73 * 101822137 * 129691841 * 5094796571297629879 * 1536021852403835577250850726481014637179

Then run CADO-NFS on each subgroup:

$ ./cado-nfs.py -dlp -ell 1536021852403835577250850726481014637179 target=82936225177577666415052331393239668755262693348731690326562114609848154162166 13579208921035624875642034521402089276606162372495774456784380935629343904605

...

Info:Log queries: Checking that log(3)=1404106513053697738808612862784757866144 is correct in base 7785272685885784582564928906403856210181547208520333383076510590456824439275...
Info:Log queries: Checking that log(3)=1404106513053697738808612862784757866144 is correct in base 7785272685885784582564928906403856210181547208520333383076510590456824439275... passed

...

Info:root: logbase = 7785272685885784582564928906403856210181547208520333383076510590456824439275
Info:root: target = 82936225177577666415052331393239668755262693348731690326562114609848154162166
Info:root: log(target) = 712407062525843960939316924588302612885 mod ell
712407062525843960939316924588302612885

Hopefully in your case is is sufficent to solve in in the largest subgroup since the exponent is small:

sage: ell=1536021852403835577250850726481014637179
sage: inverse_mod(1404106513053697738808612862784757866144,ell)*712407062525843960939316924588302612885 % ell
212223489

You would have finished the Pohlig-Hellman algorithm for larger exponent values.

The function log of Finite rings calls directly the function znlog of Pari. According to the documentation, znlog uses first the Pohlig-Hellman algorithm, to reduce to groups of prime order. Then it uses a a linear sieve index calculus method. For a faster (and parallel) implementation, you may use CADO-NFS but it will solve the discrete log only in one subgroup each time. So first you have to factorize p-1:

sage: factor(b.multiplicative_order())
factor(a.multiplicative_order())
2 * 3 * 73 * 101822137 * 129691841 * 5094796571297629879 * 1536021852403835577250850726481014637179

Then run CADO-NFS on each subgroup:

$ ./cado-nfs.py -dlp -ell 1536021852403835577250850726481014637179 target=82936225177577666415052331393239668755262693348731690326562114609848154162166 13579208921035624875642034521402089276606162372495774456784380935629343904605

...

Info:Log queries: Checking that log(3)=1404106513053697738808612862784757866144 is correct in base 7785272685885784582564928906403856210181547208520333383076510590456824439275...
Info:Log queries: Checking that log(3)=1404106513053697738808612862784757866144 is correct in base 7785272685885784582564928906403856210181547208520333383076510590456824439275... passed

...

Info:root: logbase = 7785272685885784582564928906403856210181547208520333383076510590456824439275
Info:root: target = 82936225177577666415052331393239668755262693348731690326562114609848154162166
Info:root: log(target) = 712407062525843960939316924588302612885 mod ell
712407062525843960939316924588302612885

Hopefully in your case is is sufficent to solve in in the largest subgroup since the exponent is small:

sage: ell=1536021852403835577250850726481014637179
sage: inverse_mod(1404106513053697738808612862784757866144,ell)*712407062525843960939316924588302612885 % ell
212223489

You would have finished the Pohlig-Hellman algorithm for larger exponent values.

The function log of Finite rings calls directly the function znlog of Pari. According to the documentation, znlog uses first the Pohlig-Hellman algorithm, to reduce to groups of prime order. Then it uses a a linear sieve index calculus method. For a faster (and parallel) implementation, you may use CADO-NFS but it will solve the discrete log only in one subgroup each time. So first you have to factorize p-1:$p-1$:

sage: factor(a.multiplicative_order())
2 * 3 * 73 * 101822137 * 129691841 * 5094796571297629879 * 1536021852403835577250850726481014637179

Then run CADO-NFS on each subgroup:

$ ./cado-nfs.py -dlp -ell 1536021852403835577250850726481014637179 target=82936225177577666415052331393239668755262693348731690326562114609848154162166 13579208921035624875642034521402089276606162372495774456784380935629343904605

...

Info:Log queries: Checking that log(3)=1404106513053697738808612862784757866144 is correct in base 7785272685885784582564928906403856210181547208520333383076510590456824439275...
Info:Log queries: Checking that log(3)=1404106513053697738808612862784757866144 is correct in base 7785272685885784582564928906403856210181547208520333383076510590456824439275... passed

...

Info:root: logbase = 7785272685885784582564928906403856210181547208520333383076510590456824439275
Info:root: target = 82936225177577666415052331393239668755262693348731690326562114609848154162166
Info:root: log(target) = 712407062525843960939316924588302612885 mod ell
712407062525843960939316924588302612885

Hopefully in your case is is sufficent to solve in in the largest subgroup since the exponent is small:

sage: ell=1536021852403835577250850726481014637179
sage: inverse_mod(1404106513053697738808612862784757866144,ell)*712407062525843960939316924588302612885 % ell
212223489

You would have finished the Pohlig-Hellman algorithm for larger exponent values.

The function log of Finite rings calls directly the function znlog of Pari. According to the documentation, znlog uses first the Pohlig-Hellman algorithm, to reduce to groups of prime order. Then it uses a a linear sieve index calculus method. For a faster (and parallel) implementation, you may use CADO-NFS but it will solve the discrete log only in one subgroup each time. So first you have to factorize $p-1$:

sage:  a
3    
sage: factor(a.multiplicative_order())
 2 * 3 * 73 * 101822137 * 129691841 * 5094796571297629879 * 1536021852403835577250850726481014637179

Then run CADO-NFS on each subgroup:

$ ./cado-nfs.py -dlp -ell 1536021852403835577250850726481014637179 target=82936225177577666415052331393239668755262693348731690326562114609848154162166 13579208921035624875642034521402089276606162372495774456784380935629343904605

...

Info:Log queries: Checking that log(3)=1404106513053697738808612862784757866144 is correct in base 7785272685885784582564928906403856210181547208520333383076510590456824439275...
Info:Log queries: Checking that log(3)=1404106513053697738808612862784757866144 is correct in base 7785272685885784582564928906403856210181547208520333383076510590456824439275... passed

...

Info:root: logbase = 7785272685885784582564928906403856210181547208520333383076510590456824439275
Info:root: target = 82936225177577666415052331393239668755262693348731690326562114609848154162166
Info:root: log(target) = 712407062525843960939316924588302612885 mod ell
712407062525843960939316924588302612885

Hopefully in your case is is sufficent to solve in in the largest subgroup since the exponent is small:

sage: ell=1536021852403835577250850726481014637179
sage: inverse_mod(1404106513053697738808612862784757866144,ell)*712407062525843960939316924588302612885 % ell
212223489

You would have finished the Pohlig-Hellman algorithm for larger exponent values.