0
$\begingroup$

I've developed an algorithm for fast modular exponentiation modulo composite numbers with known factorization. I'm not very well versed in cryptography, so I'm wondering if any of you know of an application of this algorithm to some cryptosystem. Even if there is no cryptosystem where this can be used, I'm also interested in similar applications, like pseudorandom number generation.

The main issue that arises with doing the classic discrete logarithm with, say, ElGamal, is that solutions modulo a prime $p$ can be lifted up to $\mathbb{Z}_{p^k}^*$. This can then be lifted to a general composite $n=\prod p_i^{e_i}$. This is why I'm looking for something that avoids the possibility of a discrete logarithm to hack it.

Any ideas?

Improve this question
$\endgroup$
4
  • $\begingroup$ how do you know the algorithm is better than what's out there to begin with? $\endgroup$
    – kodlu
    Commented Jul 20, 2023 at 6:16
  • 1
    $\begingroup$ @kodlu I've researched the topic and haven't found anything, but of course you can never be too sure. Besides, this strays a bit from the point of the question. $\endgroup$
    – TheBestMagician
    Commented Jul 20, 2023 at 15:00
  • $\begingroup$ fair enough, at least tell us the efficiency of your algorithm and someone here may be able to tell you if it's likely to be of interest $\endgroup$
    – kodlu
    Commented Jul 20, 2023 at 15:27
  • $\begingroup$ @kodlu For specific composite $m$ I compute $a^n\pmod{m}$ in $\mathcal{O}(\sqrt{\log m})$ steps, assuming $\gcd(a,m)=1$ and $n$ is on the order of $\phi(m)$. $\endgroup$
    – TheBestMagician
    Commented Jul 20, 2023 at 17:33

0

Reset to default

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.