Multiplicative inverses mod n

แชร์
ฝัง
  • เผยแพร่เมื่อ 19 ม.ค. 2025

ความคิดเห็น • 55

  • @kishoresrinivas6322
    @kishoresrinivas6322 6 ปีที่แล้ว +13

    If you have cryptography exam, remember this is the best video to learn multiplicative inverse mod n, so don't skip, just because it's above 10 min.

  • @Bayckun
    @Bayckun 3 ปีที่แล้ว +2

    7:23 I'm 80-90% sure it's supposed to be "3 = 1(3) + 0" instead but I'm not sure.

  • @Asdfdyutgfd
    @Asdfdyutgfd 2 ปีที่แล้ว +1

    This is literally the best video on this on youtube!!! Great Work

  • @silentassailant3905
    @silentassailant3905 2 ปีที่แล้ว

    OMG thankyou, im literally going to write these notes down in a way that ill never forget !!!!!! tankyou

  • @lordbalmon
    @lordbalmon 10 ปีที่แล้ว +38

    3 is not equal to 1(0) + 0, but the rest was very useful :) :D

    • @Tobiasz931
      @Tobiasz931 9 ปีที่แล้ว +2

      +lordbalmon Oh good, I was wondering if I understand it correctly, or if there is a mistake. Thanks :)

    • @kudoamv
      @kudoamv 7 ปีที่แล้ว +1

      lol, I already knew it was a mistake !

  • @kratos1537
    @kratos1537 10 ปีที่แล้ว

    Very Good Video.. Helped me in understanding modular arithmetic.

  • @michaeltisher9839
    @michaeltisher9839 5 ปีที่แล้ว

    Very nice, my friend. I thoroughly enjoyed it. Keep up the good work. :)

  • @CodeXBro
    @CodeXBro 6 ปีที่แล้ว +6

    At 7:31
    There should be 3 = 1 (3) + 0
    I think 3 = 1(0) + 0 is wrong

  • @mksarav75
    @mksarav75 7 ปีที่แล้ว +1

    Excellent, crystal clear explanation.

  • @PenguFKnight
    @PenguFKnight ปีที่แล้ว +1

    8:10
    How did he make it into 4(3) there? I don't get the jump.

    • @gabrielmoreno3027
      @gabrielmoreno3027 ปีที่แล้ว

      yep you're right, he does it wrong and somehow ends up with the right answer

  • @Duxa_
    @Duxa_ 6 ปีที่แล้ว +1

    Brilliant explanation. Thank you!

  • @yifuxero9745
    @yifuxero9745 ปีที่แล้ว

    Here's an easier way. Take 11/26 and write out the continued fraction representation, = [2, 2, 1, 3]. Underneath write the convergents = [1/2, 2/5, 2/7, 11/26]. From the rightmost denominator (26), subtract the denominator to the left (7), giving 19, the answer. This rule applies to an even number of partial quotients (we have 4). For an odd number, we just record the denominator to the left of the rightmost denominator. Say we want the multiplicative inverse of 5 mod 21. We get [4, 4, 1] and underneath our convergents are [1/4, 4/17, 5/21]. Denominator to the left of the 21 is 17, the answer since 5 * 17 = 85 = 1 mod 21; (correct).

  • @MyAsdfqwe
    @MyAsdfqwe 7 ปีที่แล้ว +2

    Thank you very much for this. xy = 1 mod n is actually helped me so much.

  • @ShaliniNegi24
    @ShaliniNegi24 5 ปีที่แล้ว

    Nice explanation .

  • @gjbt9708
    @gjbt9708 6 ปีที่แล้ว

    Good explanation. Thanks

  • @charithamunasinghe7885
    @charithamunasinghe7885 7 ปีที่แล้ว

    How can u explain this.
    With the Euclidean algorithm we finally have an efficient algorithm for finding the multiplicative inverse in Zm that is much better than exhaustive search. Find the inverses in Zm of the following elements a modulo m:
    a = 7, m = 26 (affine cipher)
    Thanx

  • @darkexodus6404
    @darkexodus6404 5 ปีที่แล้ว

    Very informative.

  • @BMGRDNRJJ
    @BMGRDNRJJ 6 ปีที่แล้ว

    Letter "F" is in position 6 of the alphbet. The rest is very informative and easy to understand.

    • @Enkiarna
      @Enkiarna 2 ปีที่แล้ว +2

      It starts from 0. So A is 0, F is 5 and G is 6

    • @essgee254
      @essgee254 2 ปีที่แล้ว

      @@Enkiarna Then it would have been mod 25

    • @Enkiarna
      @Enkiarna 2 ปีที่แล้ว

      @@essgee254 No there are 26 letters so mod is 26. If it was 25 then letters could take only from 0 to 24 which would be 25 in total. So mod is 26

    • @essgee254
      @essgee254 2 ปีที่แล้ว

      @@Enkiarna so the number of letters starts from 1 but their positioning starts from 0?

    • @Enkiarna
      @Enkiarna 2 ปีที่แล้ว

      @@essgee254 Just don't overthink it. Instead of A = 1, Z = 26 it is A = 0, Z= 25. Mod is 26 because there are 26 letters.

  • @andre.queiroz
    @andre.queiroz 8 ปีที่แล้ว

    Great lecture!

  • @perla788
    @perla788 8 ปีที่แล้ว +4

    How did you know -7 is the same as 19 mod 26? Thanks

    • @leecyrus8018
      @leecyrus8018 8 ปีที่แล้ว

      I want to know too. Anyone can ans this question?

    • @wontimnot
      @wontimnot 8 ปีที่แล้ว +17

      26 + (-7) = 19

    • @jamesmeister14
      @jamesmeister14 7 ปีที่แล้ว +3

      when mapping a number to the english alphabet there are 26 possibilities and the reason we use mod 26 is to get the specific position of the corresponding letter no matter how many times it loops. So -7 is basically just going backwards seven letters from "z". Since we can't have negative numbers we make it 19 which will be equal to the same letter as -7.

    • @AmandaRodriguez-tx3du
      @AmandaRodriguez-tx3du 6 ปีที่แล้ว

      if you add 26 to -7 you'll get 19. For smaller numbers, it is easy to reduce via the mod because you can add or subtract until you're within the range of 1 to 26

  • @syedfarabi2884
    @syedfarabi2884 2 ปีที่แล้ว

    -15/2 mod 19 what will be the result? which method should I use?

  • @EmmanuelUmoh
    @EmmanuelUmoh 8 ปีที่แล้ว

    While the rest are corrent, I think 3 = 3(1) + 0 is the correct equation. Thanks for the video anyway.

  • @stefanmitchell6877
    @stefanmitchell6877 4 ปีที่แล้ว +1

    thanks bro

  • @alexgoodness6878
    @alexgoodness6878 3 ปีที่แล้ว

    why or how did you chose MOD 26?

    • @cronotekk9193
      @cronotekk9193 3 ปีที่แล้ว

      Because that is given by the affine cipher

  • @hassandjonidi1019
    @hassandjonidi1019 6 ปีที่แล้ว

    Very useful thanks

  • @paritoshmehta4048
    @paritoshmehta4048 9 ปีที่แล้ว +3

    Why is 1 mod 7 equal to 15 ?
    Is it not 1?

    • @jddantes5172
      @jddantes5172 9 ปีที่แล้ว

      +Paritosh Mehta 15 mod 7 = 1

    • @orochicc002
      @orochicc002 8 ปีที่แล้ว +3

      1 (mod 7) = {..., -13, -6, 1, 8, 15, 22, ...}

  • @particleonazock2246
    @particleonazock2246 3 ปีที่แล้ว +1

    Clear within the first four minutes

  • @ankitabasu7242
    @ankitabasu7242 6 ปีที่แล้ว

    modular multiplicative inverse{d = ee−1(mode φ(n) ) } where : e=27 and n=55 please help me calculate 'd'

  • @stefdanut123
    @stefdanut123 6 ปีที่แล้ว

    where did you get mod 26?:(

    • @nickkisel5619
      @nickkisel5619 6 ปีที่แล้ว

      Number of letters in the alphabet

    • @stefdanut123
      @stefdanut123 6 ปีที่แล้ว

      @@nickkisel5619 oh thank you man now i get it :D

  • @alsehalo6113
    @alsehalo6113 8 ปีที่แล้ว

    thanks, how i can chose the key ,what is the conditions??

    • @alsehalo6113
      @alsehalo6113 8 ปีที่แล้ว

      i tried with another key (12,3)but it did not work cuz i did not get one i

    • @CvxFous
      @CvxFous 8 ปีที่แล้ว +1

      You need coprimes, 12 and 3 aren't coprime (gcd(12,3) != 1)

  • @sumanmukhopadhyay3079
    @sumanmukhopadhyay3079 8 ปีที่แล้ว

    THANKS

  • @marcusmedina9940
    @marcusmedina9940 2 ปีที่แล้ว

    15 does not equal 1 mod 7

  • @DhirajKumar-zj4ej
    @DhirajKumar-zj4ej 5 ปีที่แล้ว +1

    i am sorry but it's not helpful

  • @impracticalchallenges9780
    @impracticalchallenges9780 5 ปีที่แล้ว

    nerd