Skip to main content
edited title
Link
user16007
  • 800
  • 1
  • 7
  • 15

Factoring and Index Calculus and duality between DL and factoring via compuational problems made easy through them

added 636 characters in body; added 14 characters in body; added 234 characters in body
Source Link
user16007
  • 800
  • 1
  • 7
  • 15

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.

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?

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.

added 45 characters in body
Source Link
user16007
  • 800
  • 1
  • 7
  • 15

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?

If factoring is in $P$, would it affect the index calculus algorithm used for Discrete Log calculation in any serious way?

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?

edited tags
Link
François G. Dorais
  • 44.4k
  • 6
  • 150
  • 233
Loading
added link
Source Link
François G. Dorais
  • 44.4k
  • 6
  • 150
  • 233
Loading
Source Link
user16007
  • 800
  • 1
  • 7
  • 15
Loading