Skip to main content
Tweeted twitter.com/#!/StackCrypto/status/298282111868215297
Further refine title
Link
fgrieu
  • 145.7k
  • 12
  • 319
  • 611

How do I derive the time complexity of encryption and decryption usingbased on modular arithmetic?

Proofread, clean title
Source Link
fgrieu
  • 145.7k
  • 12
  • 319
  • 611

How compute encrypt and decryptdo I derive the time complexity for agorithmof encryption and decryption using modular arithmetic?

I want to calculate the time complexity of two encryption and decryption algorithms.

The first one (RSA-like) has the encryption $$ C := M^e \bmod N $$ and decryption $$ M_P := C^d \bmod N. $$

Assuming $n = \log N$, $m = \log e$ and $k = \log d$, I think they have time complexities $O(n^2 · m)$ and $O(n^2 · k)$, respectively.

Are these two complexities same?

I also have another pair of algorithms, with $$ C := M · k \bmod N $$ and $$ M_P := C · k^{-1} \bmod N.$$

How does the calculation of the modular inverse $k^{-1}$$k^{-1} \bmod N$ contribute to the time complexity calculation?

How compute encrypt and decrypt time complexity for agorithm

I want to calculate the time complexity of two encryption and decryption algorithms.

The first one (RSA-like) has the encryption $$ C := M^e \bmod N $$ and decryption $$ M_P := C^d \bmod N. $$

Assuming $n = \log N$, $m = \log e$ and $k = \log d$, I think they have time complexities $O(n^2 · m)$ and $O(n^2 · k)$, respectively.

Are these two complexities same?

I also have another pair of algorithms, with $$ C := M · k \bmod N $$ and $$ M_P := C · k^{-1} \bmod N.$$

How does the calculation of the modular inverse $k^{-1}$ contribute to the complexity calculation?

How do I derive the time complexity of encryption and decryption using modular arithmetic?

I want to calculate the time complexity of two encryption and decryption algorithms.

The first one (RSA-like) has the encryption $$ C := M^e \bmod N $$ and decryption $$ M_P := C^d \bmod N. $$

Assuming $n = \log N$, $m = \log e$ and $k = \log d$, I think they have time complexities $O(n^2 · m)$ and $O(n^2 · k)$, respectively.

Are these two complexities same?

I also have another pair of algorithms, with $$ C := M · k \bmod N $$ and $$ M_P := C · k^{-1} \bmod N.$$

How does the calculation of the modular inverse $k^{-1} \bmod N$ contribute to the time complexity?

formatting the question with formulas instead of code
Source Link
Paŭlo Ebermann
  • 22.8k
  • 7
  • 81
  • 118

I trywant to calculate the time complexity for this algorithmof two encryption and decryption algorithms.because I able to compare between them

 private void encrypt()
    {
        M = new BigInteger(64,random);
        C = M.modPow(e,N);//O(n^2 * log e) Rather  O(n^2 * m) where m = log e

    }
    
    private void decrypt()
    {
        Mp = C.modPow(d, N); //O(n^2 * log d) Rather  O(n^2 * k) where k = log d
      
    }

The first one (RSA-like) has the encryption $$ C := M^e \bmod N $$ and decryption $$ M_P := C^d \bmod N. $$

Is two algorithms sameAssuming $n = \log N$, $m = \log e$ and $k = \log d$, I think they have time complexity or Nocomplexities $O(n^2 · m)$ and $O(n^2 · k)$, respectively.

alsoAre these two complexities same?

I want ask about modalso have another pair of algorithms, with $$ C := M · k \bmod N $$ and $$ M_P := C · k^{-1} \bmod N.$$

How does the calculation of the modular inverse like$k^{-1}$ contribute to the followingcomplexity calculation?

private void encrypt()
    {
        M = new BigInteger(64,random);
        C = M.multiply(k).mod(N);

    }
    
    private void decrypt()
    {
kk= k.modinverse(N);
 Mp = kk.multiply(c).mod(N); 
      
    }

I try calculate time complexity for this algorithm.because I able to compare between them

 private void encrypt()
    {
        M = new BigInteger(64,random);
        C = M.modPow(e,N);//O(n^2 * log e) Rather  O(n^2 * m) where m = log e

    }
    
    private void decrypt()
    {
        Mp = C.modPow(d, N); //O(n^2 * log d) Rather  O(n^2 * k) where k = log d
      
    }

Is two algorithms same time complexity or No.

also I want ask about mod inverse like the following

private void encrypt()
    {
        M = new BigInteger(64,random);
        C = M.multiply(k).mod(N);

    }
    
    private void decrypt()
    {
kk= k.modinverse(N);
 Mp = kk.multiply(c).mod(N); 
      
    }

I want to calculate the time complexity of two encryption and decryption algorithms.

The first one (RSA-like) has the encryption $$ C := M^e \bmod N $$ and decryption $$ M_P := C^d \bmod N. $$

Assuming $n = \log N$, $m = \log e$ and $k = \log d$, I think they have time complexities $O(n^2 · m)$ and $O(n^2 · k)$, respectively.

Are these two complexities same?

I also have another pair of algorithms, with $$ C := M · k \bmod N $$ and $$ M_P := C · k^{-1} \bmod N.$$

How does the calculation of the modular inverse $k^{-1}$ contribute to the complexity calculation?

added 288 characters in body
Source Link
almodawan
  • 161
  • 1
  • 2
  • 7
Loading
added 288 characters in body
Source Link
almodawan
  • 161
  • 1
  • 2
  • 7
Loading
added 44 characters in body
Source Link
CodesInChaos
  • 25.1k
  • 2
  • 90
  • 129
Loading
Source Link
almodawan
  • 161
  • 1
  • 2
  • 7
Loading