一定可以

祈祷这有个安静的空间，自己的空间，从刚才就祈祷着。大自然的力量真的在身边，当我发出讯号需要盒子般东西的时候，真的有人愿意给与帮助。。。所以我相信这一次我一定可以，可以找到的。。。。。
真奇怪， 把 着 写成这，也许心理也在祈祷着这里也得到平静。心的平静。。

Some thoughts

All in the sudden i feel like to write something.
Once upon of time, I would call my ex-boyfriend to help me something and i knew he could not let go our relationship, even after 2 years. One day, one of my friend pointed this issue to me only then i only realized I should play a role to help him let go in which I stopped called him up for helping me. I think this should be be way and the thing I can give him in order to help him start a new venture soon.
I have this thought is because recently i have found a gal keeps calling her ex-boyfriend even she left him 2 years ago. Maybe she was me, as a mirror that last time of me, so selfish to somehow 'using' the other party? I don't know......Just I can't express out, feel so uneasy........Maybe i could find out my own answer during my silent time in the morning for the coming days. ^^

Restaurant City Facebook

1. Truffle is ? Fungi
   
2. Tomato is ? Fruit
   
3. Rump found at? Back
   
4. Grapes grow ? Vines
   
5. Homous? chickpeas
   
6. Chinese xxx? not mango
   
7. Saffron is a ? spices
   
8. Calamari is fried? squid
   

Pohlig-Hellman Part 1 - method 2

Method 2:
We should always use this method first, if the factoring gives us more
than one prime.

let us define some of the general terms,
5^{x} congruent 3 mod 2017
so , a = 5, b =3, n = 2017
n-1 = 2016 = 2^{5} x 3^{2} x 7
so, we have 3 prime, p_{1} =2, p_{2} = 3, p_{3} =7


steps : now, we still deal with prime 3, in order to let us see
the constrast
p_{2} = 3, x congruent n_{0} mod 9 .............we
have to find n0
Let x = 9q + r .........we form this equation for
multiply 9, r is remainder
Deal with both sides
5^{x} = 3 mod 2017.........subsitute x = 9q + r
5^{9q + r} = 3 mod 2017.........raise both side power
to the rest of the prime factor
( 5^{9q + r} )^{2^5 x 7 } = 3 ^ {2^5 x 7 } mod
2017.........by doing this is to let us to cancel off all the


numbers with power of (n-1) to 1 , as theorem


a ^ {n - 1} mod n = 1, so we can cancel off


the q and to solve r
5 ^ {2016q + 224r} = 3 ^ {224} mod 2017
5 ^ { 224r} = 3 ^ {224} mod 2017
calculation:
5 ^ {5} = 1108 mod n
5 ^ {10} = 1328
5 ^ {20} = 726
5 ^ {40} = 639
5 ^ {80} = 887
5 ^ {160} = 139
5 ^ {320} = 1168
5 ^ {640} = 732


calculation:
3 ^ {7} = 170 mod n
3 ^ {14} = 662mod n
3 ^ {28} = 555 mod n
3 ^ {56} = 1441 mod n
3 ^ {112} = 988 mod n
3 ^ {224} = 1933 mod n
3 ^ {448} = 1005 mod n
3 ^ {896} = 1525 mod n


5 ^ { 224r} = 3 ^ {224} mod 2017
576 ^{ r } = 1933 mod n .............as you can see
here, r is the remainder form with multiply
of 9,
so the possible r value could be 0,1,2,3,4,5,6,7,8
Since right not giving us 1 mod n, we will cry if the
multiply is 81, the we have to test each of them
the worst is 81 times.
so, now subsitue r for possible number
when r = 2, 576 ^{ 2 } = 988
when r = 3, 576 ^{ 3 } = 294
when r = 4, 576 ^{ 4 } = 1933 ...........bingo, stop
the loop
conclude r =4, so our equation for prime 3
x congruent 4 mod 9

Pohlig-Hellman Part 1 - method 1 Options

i was struggling for one whole day to figure out the technique to use it.
Hence, I will write a few topic about this algorithmn.

1st of all, I have found there are 2 main methods to solve this kind of question.
So now, let us explore this 2 methods. We should always use method 2
first because it is fast, if it doesn't give us ans then only look for

method 1 to solve.


let us define some of the general terms,
5^{x} congruent 3 mod 2017
so , a = 5, b =3, n = 2017
n-1 = 2016 = 2^{5} x 3^{2} x 7
so, we have 3 prime, p_{1} =2, p_{2} = 3, p_{3} =7


Method 1:
Normally this is called baby steps, which as it named very tedious with a lot of steps to perform. This method for sure will let u find the answer but a lot of steps. We have to choose method wisely based on question.
We choose this method if the power of factoring prime (p) very large and method 2 does'nt help us to find the asnwer if the exponent is big.
When the fatoring only give us one prime also use this method.


step 1: Remeber formula to deal with right hand side:-
b ^ {(n-1)/p_{i}}........p is prime, raise the power of prime from 1 until the last constants.
Example above i take prime = 3 to solve
my p_{2} = 3,
FIRST, come out the equation first, raise the power of 3 less than the maximun.
this example, max exponent for 3 is 2, so we raise until 1.
And sure we will have the constants need to be solved.
let constants be c_{i}
x = c_{0}3^{0} + c_{1}3^{1}
.......see, we have constants needed to be solved,
if the power of prime 3 larger, the
longer the steps i need to deal in order to
find all my constants.


step 2: Start to solve 1st constant 0
c0 = ?, b ^ {(n-1)/p_{i}} = 3 ^ {(2016)/3} = 3 ^ {672}
calculation:
3 ^ {7} = 170 mod n
3 ^ {14} = 662mod n
3 ^ {28} = 555 mod n
3 ^ {56} = 1441 mod n
3 ^ {112} = 988 mod n
3 ^ {224} = 1933 mod n
3 ^ {448} = 1005 mod n
3 ^ {896} = 1525 mod n


3 ^ {672} = 294 mod n...............
oh no, if we see 1 mod n here ,
we are done, else we have to continue
to deal with left hand side.
Bec a^{0} = 1 mod n


step 3: Now we have to calclate left hand in order to solve constant 0
5^{x} = 3 mod 2017 ....................see, originally
3 is no power, but in step 2 we power it,
so left hand also need to power with the same
thing
(5 ^ {x}) ^ {672} ....................replace x
with equation we have formend in step 1,
x = c_
{0}3^{0} + c_{1}3^{1} = c0 + 3c1


(5 ^ {c0 + 3c1}) ^ {672} .............multiply 672
with each of the items, as u will find all the numbers
give us
(n-1)t except the current constant we want to solve.
As we
know whatever number power of (n-1)t mod n will give us 1.
Hence,
we can cancel it bec of 1. t is any integer number.
(5 ^ {672c0 + 2016c1})
5 ^ {672c0} x 5 ^{2016c1}
5 ^ {672c0} x 1
( 5 ^ {672} ) ^ {c0}
calculation:
5 ^ {5} = 1108 mod n
5 ^ {10} = 1328
5 ^ {20} = 726
5 ^ {40} = 639
5 ^ {80} = 887
5 ^ {160} = 139
5 ^ {320} = 1168
5 ^ {640} = 732


( 5 ^ {672} ) ^ {c0} = 294 ^ {c0}


NOW, put both sides to gether
294 ^ {c0} = 294 mod n, as very clear the constant
should be 1 to make both side tally.
NOTE: in baby steps
method, every time we solve the constants,
the
constants range sure less the the current prime


so, 0 <= c_{i} < 3..........current prime is 3
ans : c0 = 1


step 4: Continue to solve constant 1
c1 = ?, b ^ {(n-1)/p_{i}} = 3 ^ {(2016)/
9} ..........as u can see i raise the prime power ( bottom)
= 3 ^ {224}
= 1933 mod
n ..........since not 1 mod n, so proceed to deal left hand


step 5: Continue to solve constant 1 - left hand
5^{x} = 3 mod 2017 ....................see, originally
3 is no power, but in step 2 we power it, so left hand
also
need to power with the same thing
(5 ^ {x}) ^ {224} ....................replace x
with equation we have formend in step 1 & step 3
x = c_
{0}3^{0} + c_{1}3^{1} = 1 + 3c1
(5 ^ { 1 + 3c1}) ^ {224}


(5 ^ { 224 + 672c1})
5 ^ {224} x 5 ^{672c1}
576 x 294^ {c1}
now put both sides together
576 x 294^ {c1} = 1933 mod n .........we have to
subsitue all the possible constanst to find


the answer, c1 can be 0,1,2
when c1=1, 576 x 294 = 1933 mod n, hence c1=
1


step 6: Calculate the equation
now, subsitue all the constants into step 1 equation.
x = c_{0}3^{0} + c_{1}3^{1} = 1 + 3c1
x = 1 + 1 x 3 = 4
Hence, the equation for prime 3 is:-
x congruent 4 mod 9


Method 2: please look at another topic

RSA Cryptosystem

Every encryption will have K, so
RSA K ={ (n p q a e): ae congruent to 1 mod phi(n) },
just remember front and back are public key for encryption purpose,
the rest are private key.

so n , e are public key

encryption: e(x) = x^{e} mod n-->n , e are public key


decryption: d(y) = y^{a} mod n


where a is multiplicative invers of
e mod phi(n) --> e^{-1} mod phi (n)
since n = pq, ( p is prime, q is prime),
so phi(n) = phi(q) x phi(p)


q always bigger than p, q - p = 2d > 0
extra 2 formula : -
1) (q - p)/2 = d
2) (p + q)/2 = sqrt( n + d^{2}) ******* to be used for below step 2
[(p + q)/2]^{2} = n + d^{2}


a) How to factoring?
....as long as we can find the d to be sqrt to an integer
let n = 18923
step 1: take sqrt(18923) = 137.56
= Math.Ceiling rounds up (137.56 ) = 138

step 2: 138^{2} = 19044, 18923 + 121 = 19044
18923 + 121 = 138^{2}
formula above (2), n + d^{2}= [(p + q)/2]^{2}
........so sqrt(121) = 11 = d

step 3: now we can have 2 equation to solve the p and q
(1)........q - p = 2d , q - p = 2(11), q - p = 22
(2)........p +q = (2)138
(1) + (2) .........2q = (2)138 + 22,2q = 298,q=149
substiute q = 149 into (2).......p = (2)138 - 149 = 127


solved, n = pq, 18923 = 127 x 149


b) encryption
e(x) = x^{e} mod n, let e = 1261
encrypt x = 2, e(2) = 2^{1261} mod 18923
caculation:-
2^{10} = 1024 mod 18923 ..............all mod 18923
.......always take the previous to be square,
e.g. (2^{10} )^{2} = (1024 )^{2} mod 18923 ,2^{20} = ?
2^{20} = 1024^{2} mod 18923
= 1048576 mod 18923
= 7811

///////////// technique using calculator start /////////////////////
(....technique using calculator, **becareful,
step 1: 1024 --> 'x2' -> 'a b/c' -> 18923
....screen will appear 1024^2 ] 18923
step 2: '='....screen will appear 55.4127781
..........so we can see the number before decimal is 55, so
we minus 55
step3 : 'Ans' - 55....screen will appear 0.4127781
..........since we mod with 18923 ,
so times with 18923
step4 : 'Ans' ->'x' ->18923
....screen will appear 7811
.....p/s: if we see ans 7811.9999 then ans will be 7812,
if ans is 7811.00000888 then ans will be 7811
)end of technique
if hard to understand just use traditional way to deal with it
//////////// technique using calculator end ///////////////////

2^{40} = 7811^{2} mod 18923 = 3969
2^{80} = 3969^{2} mod 18923 = 9025
2^{160} = 9025^{2} mod 18923 = 6033
2^{320} = 6033^{2} mod 18923 = 8160
2^{640} = 8160^{2} mod 18923 = 14486


start to calculate 2^{1261} mod 18923
(^^ just like last time SPM we do decimal changed to binary)
step 1:..noted 1261 enough to be minus by 640 so we put 1 and take remainder
step 2:..noted 621 enough to be minus by 320 so we put 1 and take remainder
step 3:..noted 301 enough to be minus by 160 so we put 1 and take remainder
step 4:..noted 141 enough to be minus by 80 so we put 1 and take remainder
step 5:..noted 61 enough to be minus by 40 so we put 1 and take remainder
step 6:..noted 21 enough to be minus by 20 so we put 1 and take remainder
step 7:..noted 1 will be 2^{1}


................2^ {1} g
2^{10} = 1024
2^{20} = 7811 ..............1 ( 21- 20= 1) f
2^{40} = 3969 ..............1 ( 61- 40 = 21) e
2^{80} = 9025 ..............1 ( 141 - 80 = 61) d
2^{160} = 6033 ..............1 ( 301 - 160 = 141 ) c
2^{320} = 8160 ..............1 ( 621- 320= 301) b
2^{640} = 14486 ..............1 ( 1261 - 640 = 621) a


calculate from bottom to up:-
ans = a x b x c x d x e x f x g mod 18923
a x b mod 18923 = 14486 x 8160 mod 18923 =12702
a x b x c mod 18923 = 12702 x 6033 mod 18923 =11939
a x b x c x d mod 18923 = 11939 x 9025 mod 18923 =1913
a x b x c x d x e mod 18923 = 1913 x 3969 mod 18923 =4574
a x b x c x d x e x f mod 18923 = 4574 x 7811 mod 18923 = 890
a x b x c x d x e x f x g mod 18923 = 890 x 2 mod 18923 = 1780


......so ans, encrypt x = 2, e(2) = 2^{1261} mod 18923
encrypted of 2 is 1780


c)decryption
find the e^{-1} mod phi(n)
d(y) = y^{a} mod n


........becareful here RSA decryption is mod phi(n) NOT mod n
example:
n = 18923 , e = 1261, .........as we calculated in the beginning
so , we have ,n = pq, 18923 = 127 x 149
phi(n) = phi(p) x phi(q) ........please refer my Euler Function
phi(18923 ) = phi(127 ) x phi(149 )
= 126 x 148
= 18648............phi(n)


now, in order to decrypt we need to find multiplicative inverse of
exponent (e^{-1}) in which is 'a' in the formula..............pls
refer to my "Multiplicative Inverse"
find, e^{-1} mod phi(n) = 1261^{-1} mod 18648
= 5797..............a
d(y) = y^{a} mod n , if my friend send me 1780, so i have to
decrypt it.
d(1780) = 1780^{5797} mod 18923


start prepare calculation:-
1780^{1} ..............1
1780^{2} = 8259 mod 18923
1780^{4} = 12589 mod 18923 ..............1
1780^{8} = 2796 mod 18923
1780^{16} = 2417 mod 18923
1780^{32} = 13605 mod 18923 ..............1
1780^{64} = 10162 mod 18923
1780^{128} = 3433 mod 18923 ..............1
1780^{256} = 15383 mod 18923
1780^{512} = 4574 mod 18923 ..............1
1780^{1024} = 11561 mod 18923 ..............1
1780^{2048} = 3572 mod 18923
1780^{4096} = 5082 mod 18923 ..............1 ( 5797- 4096=1701)


5082 x 11561 =16010 x4574 =16653 x 3433 =3366 x13605 =770 x12589
=4954 x1780 = 2 mod 18923


...........congratulation, you are master ^^ haha, dont beat me.
ans is 2 ( plaintext)

Multiplicative Inverse

It can be done by using Euclidean Algorithm :

Example 1:
Find multiplicative inverse of 3 mod 26.
so let e = 3,n = 26, e^{-1} = ?


formula: gcd(e, n) , gcd(3, 26)


steps:always put bigger number at left, then only start to divide and
fill up numbers and remainder
26 = (3)
(1) 26 = 8(3) + 2
.......always take down bracket and remainder
3 = (2)
(2) 3 = 1(2) + 1
2 = 2(1) ......stop bec remainder is 0


Extended Euclidean Algorithm : to reverse it
(2)...... 3 = 1(2) + 1
........always let the equation to be 1 = ab - c , let 1 to be left
1 = 3 - 1(2)
........always replace the figure in bracket that smallest
with something, as u noted there will always is the remainder
in above calucation,
2 in (1).....26 = 8(3) + 2,
so 2 = 26 - 8(3)
1 = 3 - 1 [26 - 8(3)]
.......dont break the small bracket whenever we expand
1 = 3 - 1(26) + 8(3)
......find the common number in bracket and sum up
1 = 1(3) + 8(3) - 1(26)
1 = 9(3) - 1(26)


so, we can see 9(3), the multiplicative invers of 3 =9 mod 26,
3^{-1} = 9 mod 26


Example 2:
Find multiplicative inverse of 5 mod 26.
so let e = 5,n = 26, e^{-1} = ?


Euclidean Algorithm :
(1) 26 = 5(5) + 1
5 = 5(1)
Extended Euclidean Algorithm :
(1) 1 = 26 - 5(5)


so 5^{-1} congruent (-5) mod 26,
26 - 5 = 12
so 5^{-1} congruent 12 mod 26, ans is 12


Example 3:
Find multiplicative inverse of 1261 mod 18648.
so let e = 1261,n = 18648, e^{-1} = ?


Euclidean Algorithm :
(1) 18648 = 14(1261) + 994
(2) 1261 = 1(994) + 267
(3) 994 = 3(267) + 193
(4) 267 = 1(193) + 74
(5) 193 = 2(74) + 45
(6) 74 = 1(45) + 29
(7) 45 = 1(29) + 16
(8) 29 = 1(16) + 13
(9) 16 = 1(13) + 3
(10) 13 = 4(3) + 1
3 = 3(1)


Extended Euclidean Algorithm :
(10) 1 = 13 - 4(3)
(9) 1 = 13- 4[16-1(13)]
1 = 13- 4(16)+4(13)
1 = 5(13)- 4(16)
(8) 1 = 5[29-1(16)]- 4(16)
1 = 5(29)-5(16)- 4(16)
1 = 5(29)-9(16)
(7) 1 = 5(29)-9[45-1(29)]
1 = 5(29)-9(45)+9(29)
1 = 14(29)-9(45)
(6) 1 = 14(29)-9(45)
1 = 14[74-1(45)]-9(45)
1 = 14(74)-14(45)-9(45)
1 = 14(74)-23(45)
(5) 1 = 14(74)-23[193 - 2(74)]
1 = 14(74)-23(193) + 46(74)
1 = 60(74)-23(193)
(4) 1 = 60[267-1(193)]-23(193)
1 = 60(267)-60(193)-23(193)
1 = 60(267)-83(193)
(3) 1 = 60(267)-83[994-3(267)]
1 = 60(267)-83(994)+249(267)
1 = 309(267)-83(994)
(2) 1 = 309[1261 - 1(994)]-83(994)
1 = 309(1261) - 309(994)-83(994)
1 = 309(1261) - 392(994)
(1) 1 = 309(1261) - 392[18648 - 14(1261)]
1 = 309(1261) - 392(18648) + 5488(1261)
1 = 5795(1261) - 392(18648)

so 1261^{-1} congruent (5795) mod 18648, ans is 5795