Generating Prime Factors

Let us denote the Set of Prime Factors by X = {(n,f)} where n is integer and f is a set of prime numbers that makes up n by multiplication.

Multiplying the set X, upto N by an integer z = w^u is defined as z.X = {z.(n,f)} = {(z.n, f union w)} where w is prime, u is a positive integer and z.n <= N.

z.(n,f) returns void, if z.n > N.

generate_prime_factors(P, N) // P is the set of prime numbers upto N, N is a positive integer
{

initialize a Set of Prime Factors, X = {(1,{1})}

for all the prime numbers i in the set P in ascending order do
j= 1;
while i^j <= N do
Y = i^j.X;
X = X union Y;
j++;
end while
end for
return X

}


let us find the prime factorization of all the numbers upto N = 10:

inital state:
X = {(1,{1})}

step1: i = 2, j = 1
Y = 2.X ={(2,{1,2})}
X = X union Y = {(1,{1}), (2,{1,2})}

step2: i = 2, j=2
Y = 2^2.X = {(4,{1,2}), (8,{1,2})}
X = X union Y = {(1,{1}), (2,{1,2}), (4,{1,2}), (8,{1,2})}

step3:i = 2, j = 3
Y = 2^3.X = {(8,{1,2})}
X = X union Y = {(1,{1}), (2,{1,2}), (4,{1,2}), (8,{1,2})}

step4: i = 2, j = 4; i^j = 2^4 = 16 > N = 10
do nothing


step5: i = 3, j = 1
Y = 3.X = {(3,{1,3}), (6,{1,2,3})}
X = X union Y = {(1,{1}), (2,{1,2}), (3,{1,3}), (4,{1,2}), (6,{1,2,3}), (8,{1,2})}

step6: i = 3, j = 2
Y = 3^2.X = {(9,{1,3})}
X = X union Y = {(1,{1}), (2,{1,2}), (3,{1,3}), (4,{1,2}), (6,{1,2,3}), (8,{1,2}), (9,{1,3})}


step7: i = 3, j =3; 3^3 > 10
do nothing

step8: i = 5, j = 1
Y = 5.X = {(5,{1,5}), (10,{1,2,5})}
X = X union Y = {(1,{1}), (2,{1,2}), (3,{1,3}), (4,{1,2}), (5,{1,5}), (6,{1,2,3}), (8,{1,2}), (9,{1,3}), (10,{1,2,5})}


step9: i = 5, j = 2; 5^2 = 25
do nothing

step9: i = 7, j = 1
Y = 5.X = {(7,{1,7})}
X = X union Y = {(1,{1}), (2,{1,2}), (3,{1,3}), (4,{1,2}), (5,{1,5}), (6,{1,2,3}), (7,{1,7}), (8,{1,2}), (9,{1,3}), (10,{1,2,5})}

Juktibidda: মাছ গু খায়. মানুষ মাছ খায়. তার মানে মানুষ গু খায়

বাংলাদেশে ছোটবেলায় দেখতাম যুক্তিবিদ্দা বলে একটা বিষয় ইন্টারমিডিয়েট লেভেল এ পরানো হত. সবাই সাবজেক্ট টা নিয়া হাসি মস্করা করত. এই  সাবজেক্ট  এ  নাকি  এমন  জিনিস  শেখানো  হয়: "মাছ গু খায়. মানুষ মাছ খায়. তার মানে মানুষ  গু খায়.". দীর্ঘ পড়াশুনা বিরতির  পর  এই  বিদেশ  বিভুয়ে আবার  পড়তে  এসে  এই  যুক্তিবিদ্যা  সাবজেক্ট  টা  আমাকে  পড়তে  হচ্ছে  M.Sc. ডিগ্রী  পাওয়ার জন্য . এইখানে  এই বিষয় এ দুইটা কোর্স আছে. একটার নাম হলো Advanced Course In Computational Logic, অন্যটার নাম হলো Answer Set Programming . এই দুইটা কোর্স পড়তে গিয়ে বুঝলাম যুক্তিবিদ্যা সাবজেক্ট টাকে অহেতুক পচানো হত. মাছ গু খায় বলে মানুষ ও গু খায় প্রমান করতে হলে প্রমান করতে হবে যে মানুষ আসলে মাছ. কিন্তু মানুষ আসলে মাছ না, বরং মানুষ মাছ খায়. কেউ যদি প্রমান করতে পারে যে মানুষ আসলে মাছ তাহলেই শুধুমাত্র প্রমানিত হবে যে মানুষ গু খায়. 

If X = x1 mod m1; X = x2 mod m2; Where m1 and m2 are co-prime, x1 < m1, x2 < m2. Then there is at most one X in the interval 0 <= X < m1*m2

Solution:

X is greater than some multiple of m1 by x1, and greater than some multiple of m2 by x2. That means, we need to find out multiple of m1 and m2 which has the difference of x1 - x2 when x1 > x2. Otherwise we need to find out multiple of m1 and m2 which has the difference of x2 - x1. That means, If there exists an X, then there exists two integers r and s such that

m2*s - m1*r = x1 - x2 if x1 > x2

m1*r - m2*s = x2 - x1 otherwise

And for both of the cases X = m2*s + x2 = m1*r + x1;

Now,the next such pair of multiple of m1 and m2 can be found by adding some multple of m1 to m1*r and by adding some multiple of m2 to m2*s. But to preserve the equality these two multiples need to be equal. That means they need to be common multiple of m1 and m2. The lowest common multiple of m1 and m2 are m1*m2 as they are co-prime. 

Lets say there exist one X such that 0 <= X < m1*m2 (actually at least one such X exist which is provable but not mentioned here); Then the next possible value of X will be, X = m2*s + m1*m2 + x2 = m1*r + m1*m2 + x1 >= m1*m2

That means there exist at most one X such that 0 <= X < m1*m2

Calculating LCM

Problem
2520 is the smallest number that can be divided by each of the numbers from 1 to 10 without any remainder. What is the smallest positive number that is evenly divisible by all of the numbers from 1 to 20?

Solution:

Let X be a set of integers. 

|X| = N and xi is element of X where i is an element of the set {1,2, ... ,N} . Then,

LCM(x1,x2,.....,xN) = LCM(LCM(x1,x2,.....,xN-1),xN) and

LCM(x,y) = (x*y)/GCD(x,y) where x,y are any positive integer

LCM stands for Lowest Common Multiple. and GCD stands Greatest Common Divisor.Calculating GCD is a very efficient algorithm given by the great Euclid. It is called the grand daddy of all algorithm. The oldest algorithm that exists today and still play a great role in computer science.

Detail Work Out:

Let, X = {1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20}

(Read the black font from top to bottom, and blue font from bottom to top)

LCM(1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20) = LCM(LCM(1,2,3,4,5,6,7,8,9,1011,12,13,14,15,16,17,18,19),20)

LCM(1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19) = LCM(LCM(1,2,3,4,5,6,7,8,9,1011,12,13,14,15,16,17,18),19)

LCM(1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18) = LCM(LCM(1,2,3,4,5,6,7,8,9,1011,12,13,14,15,16,17),18)

LCM(1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17) = LCM(LCM(1,2,3,4,5,6,7,8,9,1011,12,13,14,15,16),17)

LCM(1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16) = LCM(LCM(1,2,3,4,5,6,7,8,9,1011,12,13,14,15),16)

LCM(1,2,3,4,5,6,7,8,9,10,11,12,13,14,15) = LCM(LCM(1,2,3,4,5,6,7,8,9,1011,12,13,14),15)

LCM(1,2,3,4,5,6,7,8,9,10,11,12,13,14) = LCM(LCM(1,2,3,4,5,6,7,8,9,1011,12,13),14)

LCM(1,2,3,4,5,6,7,8,9,10,11,12,13) = LCM(LCM(1,2,3,4,5,6,7,8,9,1011,12),13)

LCM(1,2,3,4,5,6,7,8,9,10,11,12) = LCM(LCM(1,2,3,4,5,6,7,8,9,10,11),12)

LCM(1,2,3,4,5,6,7,8,9,10,11) = LCM(LCM(1,2,3,4,5,6,7,8,9,10),11)

LCM(1,2,3,4,5,6,7,8,9,10) = LCM(LCM(1,2,3,4,5,6,7,8,9),10)

LCM(1,2,3,4,5,6,7,8,9) = LCM(LCM(1,2,3,4,5,6,7,8),9) 

LCM(1,2,3,4,5,6,7,8) = LCM(LCM(1,2,3,4,5,6,7),8)

LCM(1,2,3,4,5,6,7) = LCM(LCM(1,2,3,4,5,6),7)

LCM(1,2,3,4,5,6) = LCM(LCM(1,2,3,4,5),6) 

LCM(1,2,3,4,5,6) = LCM(60,6) = (60*6)/GCD(60,6) = 60

LCM(1,2,3,4,5) = LCM(LCM(1,2,3,4),5)

LCM(1,2,3,4,5) = LCM(12,5) = (12*5)/GCD(12,5) = 60

LCM(1,2,3,4) = LCM(LCM(1,2,3),4)

LCM(1,2,3,4) = LCM(6,4) = (6*4)/GCD(6,4) = 12 

LCM(1,2,3) = LCM(LCM(1,2),3) 

LCM(1,2,3) = LCM(2,3) = (2*3)/GCD(2,3) = 6 

Now we know,

LCM(1,2) = (1*2)/GCD(1,2) = 2/1 = 2

So, now we calculate the whole thing backwards. (As like it is done in recursion in programming). It takes N-1 steps. 

Modular Arithmatic

Problem Statement:

Let p and q are prime. x be an integer such that
x mod p = 1 and
x mod q = 1

Prove that, x mod pq =1

Solution:

An Observation: The least common multiple of two integers divide all the common multiples of those two integers. This observation can also be proved algebraically. The algebraic proof is not mentioned here.

Now,
x mod p = 1 means, p divides x-1
x mod q = 1 means, q divides x-1

That means x-1 is a common multiple of p and q.

pq is also a common multiple of p and q.

Let us denote the LCM of p and q by LCM(p,q) and GCD of p and q by GCD(p,q).

We know that the LCM of any two integers is obtained by dividing the the product of the two integers by their GCD. That is:  LCM(p,q) = pq/GCD(p,q)

As both p and q are prime, LCM(p,q) = pq

So, from the first statement(Observation) of this solution, we can write that pq divides x - 1

That means x mod pq =1 ( Proved )


Note: I am happy if it helps.

All Intermediate Values of Block Cipher PRESENT: One Example

Initial Key:	ff	ff	ff	ff	ff	ff	ff	ff	ff	ff
Key(80b) use at 01th Rnd:	ff	ff	ff	ff	ff	ff	ff	ff	ff	ff
Key(80b) use at 02th Rnd:	2f	ff	ff	ff	ff	ff	ff	ff	7f	ff
Key(80b) use at 03th Rnd:	1f	ff	e5	ff	ff	ff	ff	fe	ff	ff
Key(80b) use at 04th Rnd:	7f	ff	e3	ff	fc	bf	ff	fe	7f	ff
Key(80b) use at 05th Rnd:	4f	ff	ef	ff	fc	7f	ff	95	ff	ff
Key(80b) use at 06th Rnd:	8f	ff	e9	ff	fd	ff	ff	8d	7f	f2
Key(80b) use at 07th Rnd:	ff	fe	51	ff	fd	3f	ff	bc	ff	f1
Key(80b) use at 08th Rnd:	ef	fe	3f	ff	ca	3f	ff	a4	7f	f7
Key(80b) use at 09th Rnd:	3f	fe	fd	ff	c7	ff	f9	43	ff	f4
Key(80b) use at 10th Rnd:	df	fe	87	ff	df	bf	f8	fb	7f	28
Key(80b) use at 11th Rnd:	af	e5	1b	ff	d0	ff	fb	f2	ff	1f
Key(80b) use at 12th Rnd:	0f	e3	f5	fc	a3	7f	fa	1a	7f	7e
Key(80b) use at 13th Rnd:	9f	ef	c1	fc	7e	bf	94	69	ff	43
Key(80b) use at 14th Rnd:	bf	e8	73	fd	f8	3f	8f	d1	72	8d
Key(80b) use at 15th Rnd:	6e	51	b7	fd	0e	7f	bf	0	f1	fa
Key(80b) use at 16th Rnd:	5e	3f	4d	ca	36	ff	a1	c8	77	e0
Key(80b) use at 17th Rnd:	ce	fc	0b	c7	e9	b9	46	d7	f4	39
Key(80b) use at 18th Rnd:	2e	87	39	df	81	78	fd	3f	a8	da
Key(80b) use at 19th Rnd:	25	1b	45	d0	e7	3b	f0	26	1f	a7
Key(80b) use at 20th Rnd:	43	f4	e4	a3	68	ba	1c	ee	fe	04
Key(80b) use at 21th Rnd:	7f	c0	88	7e	9c	94	6d	1d	43	9d
Key(80b) use at 22th Rnd:	f8	73	af	f8	11	0f	d3	98	0d	a3
Key(80b) use at 23th Rnd:	c1	b4	7f	0e	75	ff	2	2a	fa	73
Key(80b) use at 24th Rnd:	0f	4e	78	36	8f	e1	ce	b4	60	45
Key(80b) use at 25th Rnd:	3c	8	a1	e9	cf	6	d1	f0	39	d6
Key(80b) use at 26th Rnd:	c7	3a	c7	81	14	3d	39	ec	5a	3e
Key(80b) use at 27th Rnd:	3b	47	d8	e7	58	f0	22	8a	a7	3d
Key(80b) use at 28th Rnd:	04	e7	a7	68	fb	1c	eb	13	84	51
Key(80b) use at 29th Rnd:	d0	8a	20	9c	f4	ed	1f	6d	9d	62
Key(80b) use at 30th Rnd:	83	ac	5a	11	44	13	9e	93	23	ed
Key(80b) use at 31th Rnd:	a4	7d	b0	75	8b	42	28	8d	73	d2
Key(80b) use at 32th Rnd:	fe	7a	54	8f	b6	0e	b1	67	c5	11
Plaintext:	ff	ff	ff	ff	ff	ff	ff	ff
Round 01 Starts
Round Key:	ff	ff	ff	ff	ff	ff	ff	ff
State after addRoundKey:	0	0	0	0	0	0	0	0
State after sBoxLayer:	cc	cc	cc	cc	cc	cc	cc	cc
State after pLayer:	ff	ff	ff	ff	0	0	0	0
Round 02 Starts
Round Key:	2f	ff	ff	ff	ff	ff	ff	ff
State after addRoundKey:	d0	0	0	0	ff	ff	ff	ff
State after sBoxLayer:	7c	cc	cc	cc	22	22	22	22
State after pLayer:	7f	0	ff	0	80	ff	80	0
Round 03 Starts
Round Key:	1f	ff	e5	ff	ff	ff	ff	fe
State after addRoundKey:	60	ff	1a	ff	7f	0	7f	fe
State after sBoxLayer:	ac	22	5f	22	d2	cc	d2	21
State after pLayer:	c4	b8	4c	b8	b7	46	0c	89
Round 04 Starts
Round Key:	7f	ff	e3	ff	fc	bf	ff	fe
State after addRoundKey:	bb	47	af	47	4b	f9	f3	77
State after sBoxLayer:	88	9d	f2	9d	98	2e	2b	dd
State after pLayer:	fb	d7	19	13	0c	3c	3b	87
Round 05 Starts
Round Key:	4f	ff	ef	ff	fc	7f	ff	95
State after addRoundKey:	b4	28	f6	ec	f0	43	c4	12
State after sBoxLayer:	89	63	2a	14	2c	9b	49	56
State after pLayer:	c4	74	21	4b	3c	91	52	36
Round 06 Starts
Round Key:	8f	ff	e9	ff	fd	ff	ff	8d
State after addRoundKey:	4b	8b	c8	b4	c1	6e	ad	bb
State after sBoxLayer:	98	38	43	89	45	a1	f7	88
State after pLayer:	d3	2b	8	cc	24	2c	a5	5c
Round 07 Starts
Round Key:	ff	fe	51	ff	fd	3f	ff	bc
State after addRoundKey:	2c	d5	59	33	d9	13	5a	e0
State after sBoxLayer:	64	70	0e	bb	7e	5b	0f	1c
State after pLayer:	7	55	e4	e5	a7	d4	23	b6
Round 08 Starts
Round Key:	ef	fe	3f	ff	ca	3f	ff	a4
State after addRoundKey:	e8	ab	db	1a	6d	eb	dc	12
State after sBoxLayer:	13	f8	78	5f	a7	18	74	56
State after pLayer:	35	90	2b	4f	69	c9	eb	6a
Round 09 Starts
Round Key:	3f	fe	fd	ff	c7	ff	f9	43
State after addRoundKey:	0a	6e	d6	b0	ae	36	12	29
State after sBoxLayer:	cf	a1	7a	8c	f1	ba	56	6e
State after pLayer:	e7	b1	c9	8f	6c	b7	58	e8
Round 10 Starts
Round Key:	df	fe	87	ff	df	bf	f8	fb
State after addRoundKey:	38	4f	4e	70	b3	8	a0	13
State after sBoxLayer:	b3	92	91	dc	8b	c3	fc	5b
State after pLayer:	ab	ed	3	2e	d0	59	ee	5b
Round 11 Starts
Round Key:	af	e5	1b	ff	d0	ff	fb	f2
State after addRoundKey:	4	8	18	d1	0	a6	15	a9
State after sBoxLayer:	c9	c3	53	75	cc	fa	50	fe
State after pLayer:	e0	f3	ab	eb	16	33	5f	2a
Round 12 Starts
Round Key:	0f	e3	f5	fc	a3	7f	fa	1a
State after addRoundKey:	ef	10	5e	17	b5	4c	a5	30
State after sBoxLayer:	12	5c	1	5d	80	94	f0	bc
State after pLayer:	11	ab	33	19	40	0a	a7	2a
Round 13 Starts
Round Key:	9f	ef	c1	fc	7e	bf	94	69
State after addRoundKey:	8e	44	f2	e5	3e	b5	33	43
State after sBoxLayer:	31	99	26	10	b1	80	bb	9b
State after pLayer:	30	af	4	0	8c	8d	f2	cf
Round 14 Starts
Round Key:	bf	e8	73	fd	f8	3f	8f	d1
State after addRoundKey:	8f	47	77	fd	74	b2	7d	1e
State after sBoxLayer:	32	9d	dd	27	d9	86	d7	51
State after pLayer:	3c	e8	1d	9e	c3	14	bd	cf
Round 15 Starts
Round Key:	6e	51	b7	fd	0e	7f	bf	0
State after addRoundKey:	52	b9	aa	63	cd	6b	2	cf
State after sBoxLayer:	6	8e	ff	ab	47	a8	c6	42
State after pLayer:	3f	38	5c	ce	5f	65	0d	40
Round 16 Starts
Round Key:	5e	3f	4d	ca	36	ff	a1	c8
State after addRoundKey:	61	7	11	4	69	9a	ac	88
State after sBoxLayer:	a5	cd	55	c9	ae	ef	f4	33
State after pLayer:	b3	f8	7e	7c	80	fb	5d	1b
Round 17 Starts
Round Key:	ce	fc	0b	c7	e9	b9	46	d7
State after addRoundKey:	7d	4	75	bb	69	42	1b	cc
State after sBoxLayer:	d7	c9	d0	88	ae	96	58	44
State after pLayer:	bb	e4	e8	5b	40	d0	d8	28
Round 18 Starts
Round Key:	2e	87	39	df	81	78	fd	3f
State after addRoundKey:	95	63	d1	84	c1	a8	25	17
State after sBoxLayer:	e0	ab	75	39	45	f3	60	5d
State after pLayer:	b1	21	8c	eb	ba	38	1f	73
Round 19 Starts
Round Key:	25	1b	45	d0	e7	3b	f0	26
State after addRoundKey:	94	3a	c9	3b	5d	3	ef	55
State after sBoxLayer:	e9	bf	4e	b8	7	cb	12	0
State after pLayer:	f7	30	9c	60	b6	54	72	58
Round 20 Starts
Round Key:	43	f4	e4	a3	68	ba	1c	ee
State after addRoundKey:	b4	c4	78	c3	de	ee	6e	b6
State after sBoxLayer:	89	49	d3	4b	71	11	a1	8a
State after pLayer:	d9	0b	2a	80	5	89	5d	f4
Round 21 Starts
Round Key:	7f	c0	88	7e	9c	94	6d	1d
State after addRoundKey:	a6	cb	a2	fe	99	1d	30	e9
State after sBoxLayer:	fa	48	f6	21	ee	57	bc	1e
State after pLayer:	d8	cd	ac	f5	ce	d9	89	3a
Round 22 Starts
Round Key:	f8	73	af	f8	11	0f	d3	98
State after addRoundKey:	20	be	3	0d	df	d6	5a	a2
State after sBoxLayer:	6c	81	cb	c7	72	7a	0f	f6
State after pLayer:	6e	16	cb	a7	85	f7	15	a6
Round 23 Starts
Round Key:	c1	b4	7f	0e	75	ff	2	2a
State after addRoundKey:	af	a2	b4	a9	f0	8	17	8c
State after sBoxLayer:	f2	f6	89	fe	2c	c3	5d	34
State after pLayer:	af	64	b3	6d	f3	92	a6	1e
Round 24 Starts
Round Key:	0f	4e	78	36	8f	e1	ce	b4
State after addRoundKey:	a0	2a	cb	5b	7c	73	68	aa
State after sBoxLayer:	fc	6f	48	8	d4	db	a3	ff
State after pLayer:	d5	bb	f8	e3	b0	1f	90	b7
Round 25 Starts
Round Key:	3c	8	a1	e9	cf	6	d1	f0
State after addRoundKey:	e9	b3	59	0a	7f	19	41	47
State after sBoxLayer:	1e	8b	0e	cf	d2	5e	95	9d
State after pLayer:	77	9b	47	b5	55	50	91	af
Round 26 Starts
Round Key:	c7	3a	c7	81	14	3d	39	ec
State after addRoundKey:	b0	a1	80	34	41	6d	a8	43
State after sBoxLayer:	8c	f5	3c	b9	95	a7	f3	9b
State after pLayer:	e7	ab	74	58	2a	3d	3b	df
Round 27 Starts
Round Key:	3b	47	d8	e7	58	f0	22	8a
State after addRoundKey:	dc	ec	ac	bf	72	cd	19	55
State after sBoxLayer:	74	14	f4	82	d6	47	5e	0
State after pLayer:	0a	84	dc	fc	89	54	a8	98
Round 28 Starts
Round Key:	4	e7	a7	68	fb	1c	eb	13
State after addRoundKey:	0e	63	7b	94	72	48	43	8b
State after sBoxLayer:	c1	ab	d8	e9	d6	93	9b	38
State after pLayer:	bf	ad	8a	c0	32	56	59	be
Round 29 Starts
Round Key:	d0	8a	20	9c	f4	ed	1f	6d
State after addRoundKey:	6f	27	aa	5c	c6	bb	46	d3
State after sBoxLayer:	a2	6d	ff	4	4a	88	9a	7b
State after pLayer:	9c	7d	3d	82	ec	47	1c	0b
Round 30 Starts
Round Key:	83	ac	5a	11	44	13	9e	93
State after addRoundKey:	1f	d1	67	93	a8	54	82	98
State after sBoxLayer:	52	75	ad	eb	f3	9	36	e3
State after pLayer:	0f	92	b6	86	6b	cf	b5	d9
Round 31 Starts
Round Key:	a4	7d	b0	75	8b	42	28	8d
State after addRoundKey:	ab	ef	6	f3	e0	8d	9d	54
State after sBoxLayer:	f8	12	ca	2b	1c	37	e7	9
State after pLayer:	cd	49	88	5c	97	3c	a1	b5
The Final(32) addRoundKey Starts
Round Key:	fe	7a	54	8f	b6	0e	b1	67
The ciphertex is:	33	33	dc	d3	21	32	10	d2