why factorisation and cracking rsa is hard
The fundamental theorem of arithmetic says that "factorization of every composite number can be expressed as a product of primes irrespective of the order in which the prime factors of that respective number occurs". The fundamental theorem of arithmetic is a very useful method to understand the prime factorization of any number. Take counting 5 9 1 = 5*100+9*10+1 This is encoded optimally, every number encoded like this is encoded with equal probability, there is no room for encoding of factors, these are figured out by brute force trial division or some other expensive factoring algorithm. A number scheme which encodes factors can be made e.g encode the numbers with factors 8=2 2 2 6=2 3 This makes factorisation redundant This is not done however and the encoding of numbers is optimal leaving no space for encoding factors which can be found by gaussian elimination or similar in a bitwise checking of the 2 factors of the product. Also in mult...