#5999: faster recognise if there is no discrete log
---------------------------+------------------------------------------------
Reporter: gerrob | Owner: was
Type: defect | Status: new
Priority: major | Milestone: sage-4.0
Component: number theory | Keywords: discrete log, factor
---------------------------+------------------------------------------------
Just one example:
sage: n=15*(factorial(54)+1);a=Mod(8,n);b=Mod(7,n);discrete_log(a,b)
And this takes lots of time, because sage first factorize n, and this
takes about 4 minutes on my pc. However after finding 3 and 5 as
primefactors of n you can immediately observe that {{{7^x==8 mod 15}}} is
unsolvable so the original problem also.
So the idea is that: get "small" prime(power) divisors of n by trial
division/another method, and when you find a primepower divisor then check
if the problem is still solvable or not.
--
Ticket URL: <http://trac.sagemath.org/sage_trac/ticket/5999>
Sage <http://sagemath.org/>
Sage - Open Source Mathematical Software: Building the Car Instead of
Reinventing the Wheel
--~--~---------~--~----~------------~-------~--~----~
You received this message because you are subscribed to the Google Groups
"sage-trac" group.
To post to this group, send email to [email protected]
To unsubscribe from this group, send email to
[email protected]
For more options, visit this group at
http://groups.google.com/group/sage-trac?hl=en
-~----------~----~----~----~------~----~------~--~---
