« first day (2077 days earlier)      last day (2594 days later) » 

CurveEnthusiast
CurveEnthusiast
5:23 PM
@Evinda Do you need a strict upper bound? You can also compute $g^{-1}$ as an exponentiation $g^{\varphi(N)-1}$. This has perhaps a more obvious upper bound of $2\log N$ group operations compared to the Euclidean algorithm. The multiplication $y\cdot g^{-1}\mod N$ is a single group operation, so we need at most $2\log N+1$ operations.
There are several ways to make this stricter.
 
 
3 hours later…
Evinda
Evinda
8:05 PM
Why does it hold that $g^{-1}=g^{\phi(N)-1}$ ? Why do we need $2 \log{N}$ group operations to compute it? @CurveEnthusiast
 
SEJPM
SEJPM
@Evinda for the second part: repeated square and multiply
Exponentiation by squaring
In mathematics and computer programming, exponentiating by squaring is a general method for fast computation of large positive integer powers of a number, or more generally of an element of a semigroup, like a polynomial or a square matrix. Some variants are commonly referred to as square-and-multiply algorithms or binary exponentiation. These can be of quite general use, for example in modular arithmetic or powering of matrices. For semigroups for which additive notation is commonly used, like elliptic curves used in cryptography, this method is also referred to as double-and-add. == Basic... ==
for the first part, that is because we work on the order of the group
Order (group theory)
In group theory, a branch of mathematics, the term order is used in two unrelated senses: The order of a group is its cardinality, i.e., the number of elements in its set. Also, the order, sometimes period, of an element a of a group is the smallest positive integer m such that am = e (where e denotes the identity element of the group, and am denotes the product of m copies of a). If no such m exists, a is said to have infinite order. The ordering relation of a partially or totally ordered group. This article is about the first sense of order. The order of a group G is denoted by ord(G) or | G...
and for the order we can calculate in $\mathbb Z_{\lambda(N)}$
Carmichael function
In number theory, the Carmichael function of a positive integer n, denoted λ ( n ) {\displaystyle \lambda (n)} , is defined as the smallest positive integer m such that a m ≡ 1 ( mod n ) {\displaystyle a^{m}\equiv 1{\pmod {n}}} for every integer a that is coprime to n. In more algebraic terms, it defines the exponent of the multiplicative group...
ie we can reduce every value $\bmod{\lambda(n)}$ (or if it's easier $\bmod{\varphi(n)}$
and $\varphi(N)-1\equiv -1\pmod{\varphi(N)}$
 
CurveEnthusiast
CurveEnthusiast
8:29 PM
@Evinda What SEJPM says! It follows from Euler's Theorem, which is a very useful result to know. The second part is indeed based on the square-and-multiply algorithm.
 
 
2 hours later…
Evinda
Evinda
10:29 PM
@CurveEnthusiast @SEJPM
In my notes I found the following algorithm for repeated squaring:
power g n=
P=1
while n>0 do
(n',r)=div_rem(n,2)
if r==1 then P=Pg
n=n'
g=g^2
It says that the division with remainder requires $O(\log^2{n})$ time
$2\log n$ operations in the group are made
But if we need $O(\log^2{n})$ time for the division , can't we also use the extended euclidean algorithm?
And something else... we said in class that for the multiplication of the numbers n and m we need $O(\log{n} \log{m})$ time. So we don't see multiplication as one step. Do we? @SEJPM
 

« first day (2077 days earlier)      last day (2594 days later) »