I want to prove if the composite are equal to each other

  • Thread starter Thread starter behzad_b
  • Start date Start date
  • Tags Tags
    Composite
behzad_b
Messages
1
Reaction score
0
Given f:{0,1}n→{0,1}n, define f′:{0,1}2n→{0,1}2n as follows: for x,r∈{0,1}n define f′(x∘r):=f(x)∘r (where ∘ denotes concatenation). Prove that if f(⋅) is one way permutation then so is f′(⋅).

i don't understand f′(x∘r):=f(x)∘r how to decompose it in order to prove it

I tried proving it by using a composition of tow bijection, as a permutation is a sect of bijection function.

I am stuck on the proof, I don't know how to do the proof
 
Physics news on Phys.org
What is the definition of {0,1}n?
 
Do you mean ##\{0,1\}^n##?

What is a "one way" permutation?
 
There are two things I don't understand about this problem. First, when finding the nth root of a number, there should in theory be n solutions. However, the formula produces n+1 roots. Here is how. The first root is simply ##\left(r\right)^{\left(\frac{1}{n}\right)}##. Then you multiply this first root by n additional expressions given by the formula, as you go through k=0,1,...n-1. So you end up with n+1 roots, which cannot be correct. Let me illustrate what I mean. For this...
Back
Top