On discrete logs

kpatsak · 2008-02-19, 03:08

Hi,
I'd like to know if there's a class of prime numbers where the discrete log can be computed more efficiently, or if there's an algorithm(besides brute force) that can speed up the computation of discrete log when knowing an upper bound

maxal · 2008-02-19, 04:44

time to compute discrete logs modulo prime p is very sensitive to prime factorization of p-1. in particular, it becomes easy if all prime factors of p-1 are small, and hard if p-1 has a large prime factor.

as of algorithms - take a look at http://www.cs.toronto.edu/~cvs/dlog/

2008-02-19, 03:08	#1
kpatsak Oct 2007 3₁₆ Posts	On discrete logs Hi, I'd like to know if there's a class of prime numbers where the discrete log can be computed more efficiently, or if there's an algorithm(besides brute force) that can speed up the computation of discrete log when knowing an upper bound

Similar Threads
Thread	Thread Starter	Forum	Replies	Last Post
NFS@Home msieve logs for pastebin url	pinhodecarlos	NFS@Home	316	2021-02-15 12:49
Der Geoibils now require logs+nuts(to be pronounced with New Joisey accent)	c10ck3r	Lounge	8	2013-11-18 22:57
Didn't get the credits and no server logs	joblack	PrimeNet	5	2010-07-02 22:31
llrnet Server Date/Time stamps in logs	IronBits	No Prime Left Behind	30	2008-11-20 14:59
Converting Logs	Numbers	Math	5	2005-08-14 06:29

2008-02-19, 04:44	#2
maxal Feb 2005 2²×3²×7 Posts	time to compute discrete logs modulo prime p is very sensitive to prime factorization of p-1. in particular, it becomes easy if all prime factors of p-1 are small, and hard if p-1 has a large prime factor. as of algorithms - take a look at http://www.cs.toronto.edu/~cvs/dlog/