Skip to main content
5 of 6
added 636 characters in body; added 14 characters in body; added 234 characters in body
user16007
  • 800
  • 1
  • 7
  • 15

Factoring and Index Calculus

If factoring is in $P$ (with a blazing fast polynomial time in $P$), would it affect the index calculus algorithm used for Discrete Log calculation in any serious way?

Other connections

$1.)$ "Number field cryptography" Johannes Buchmann Tsuyoshi Takagi Ulrich Vollmer

The above paper mentions Root Problem (RP) and Group Order Problem (GOP) is same as factoring discriminant. So factoring easy implies RP and GOP are easy.

$2.)$ "A Signature Scheme Based on the Intractability of Computing Roots" Ingrid Biehl Johannes Buchmann Safuat Hamdy Andreas Meyer

The above paper mentions if DL is easy, Group Order Problem (GOP) is easy which inturn would imply Root Problem (RP) would be easy. So DL is easy implies RP and GOP are easy.

Though unrelated to index calculus directly, could any of these links be used to show index calculus for DL could be done faster than $O(\sqrt{P})$ if factorization is quick?

There seems to be some kind of duality between DL and factoring since both lead to easy solutions for RP and GOP.

user16007
  • 800
  • 1
  • 7
  • 15