Tag Info

New answers tagged

0

It appears, braid groups are indeed a good bet, and you can do Diffie-Hellman on them, see Braid Group Cryptography.


1

First there are the "generic" discrete logarithm algorithms like Shanks's "baby step, giant step" and Pollard's $\rho$, which run in $O(\sqrt{L})$ and are thus of exponential complexity (in the size of $L$). Those algorithms work in virtually any group. In the special case of the multiplicative groups of finite fields, we have subexponential algorithms ...


2

There are some errors in the basic assumptions or in their descriptions. So, we start with the group $\mathbb{Z}_p^*$, with $p$ prime. This is a cyclic group with order $p-1$. if a number is said to be a subgroup of a quadratic residue of Z∗p, can I affirm that it is a generator of a cyclic group ? First, a number (or more formally an element of the ...


2

To search for the values $a^x$ in the range $0 < x < k$, what you need to do is set $m = \sqrt{k}$ (rounded up), and then do the Baby Step/Giant Step algorithm for $0 \le i, j < m$. That is, you generate the values $a^0, a^1, ..., a^{m-1}$ and the values $B\cdot a^{-0}, B\cdot a^{-m}, B\cdot a^{-2m}, ..., B\cdot a^{-(m-1)m}$; if $x<k$, then ...


7

Does the factorization of N somehow help me? It sure does. I think I could compute the logarithm modulo each prime and then combine it, but do not know how exactly. Seems similar like problems for Chinese remainder theorem but I cannot find the way how to do it. You're real close; you do recombine them using the Chinese Remainder Theorem; however ...



Top 50 recent answers are included