Results 1 to 2 of 2

Math Help - Help Verifying/Completing Basic Cryptography Proofs

  1. #1
    Junior Member
    Joined
    Apr 2013
    From
    Canada
    Posts
    42
    Thanks
    2

    Help Verifying/Completing Basic Cryptography Proofs

    I'm not sure if there's a lot of different types of notation for this stuff, but just to be clear S(a) means the support of a, w(a) means the weight of a, h(a,b) is the hamming distance between a and b, \mu(C) is the minimum hamming distance between any two words in the group code C, and S(a;b) is a sphere where a is the center and b is the radius.

    1. "Given $\alpha \in Z^{n}_{2}$ and a nonnegative integer r, find a formula for |S( $\alpha$;r)|. Use it to find |S(0110101;4)|"

    For this one I said |S( $\alpha$;r)| = $\sum^{r}_{i=0} \dfrac{n!}{i!(n-i)!}$
    Substituting 7 for n and 4 for r, I got |S(0110101;4)| = $\sum^{4}_{i=0} \dfrac{7!}{i!(7-i)!} $= 99

    2. "If C is a code contained in $Z^{n}_{2}$ and $\alpha$ a fixed word in $Z^{n}_{2}$ , prove that $\mu(C) =  \mu(C + \alpha)$ where $C + \alpha = \{\gamma +  \alpha|\gamma \in C\}$ "

    By adding $\alpha$ to words \gamma_1 $and$ \gamma_2 \in C, $h(\gamma_1,\gamma_2)$ is unchanged since each coordinate position i in $\gamma_1$ that gets changed is also changed in $\gamma_2$ (with each coordinate position $i \in  S(\alpha)$.
    The hamming distance between any two elements of C are unchanged when $\alpha$ is added to all of them, therefore the minimum hamming distance of C is equal to the minimum hamming distance of C + $\alpha$.

    3. "For $\alpha \in  Z^{n}_{2}$ and any nonnegative real number r, define $S(\alpha;r) = \{\gamma | h(\alpha,\gamma)\leq r\}$. Prove that if $\alpha,\beta \in Z^{n}_{2}$ and p and q are nonnegative integers, then $S(\alpha;p) \cap S(\beta;q) \neq  \varnothing$ if and only if $h(\alpha,\gamma) \leq p +  q$."

    Consider the following 3 possible Cases:
    Case 1:
    If $S(\alpha;p) \cap S(\beta;q) = {\gamma}$, then $h(\alpha,\beta) = p+q$
    Case 2:
    Let k < n, k \in Z
    If $S(\alpha;p) \cap S(\beta;q) = {\gamma_1,\gamma_2, ..., \gamma_k}$, then $h(\alpha,\beta) < p+q$
    Case 3:
    $S(\alpha;p) \cap S(\beta;q) = {\varnothing}$, then $h(\alpha,\beta) > p+q$

    Therefore $S(\alpha;p) \cap S(\beta;q) \neq \varnothing$ implies $h(\alpha,\beta) \leq p+q$

    So I did the "if" part, but I'm not sure how to do the "only if" part or if that's necessary (I've seen proofs that said it's ok to omit it, but I don't know when that's true?)

    4. "Let $\alpha =  a_{1}a_{2}...a_{n}$ and $\beta = b_{1}b_{2}...b_{n}$ be words of $Z^{n}_{2}$. Define $\alpha \bullet \beta$ to be $a_{1}b_{1} + a_{2}b_{2} +...+  a_{n}b_{n}$ (ie $110101 \bullet 101101 = 1$). Let C be an (n,k) code (code of length n with n-k check digits) and define $ C^{\bot} = \{\alpha \in  Z^{n}_{2} | \alpha \bullet \beta = 0, \forall \beta \in C\}$. This is the so-called dual of C.
    (i) Prove $C^{\bot}$ is a subgroup of $Z^{n}_{2}$
    (ii) Prove that if M is the generator matrix of C, then C^{\bot} = ker  F_{M^{T}} where M^{T} is the transpose of M, i.e., the matrix obtained by interchanging rows and columns. Hence show that |C^{\bot}| = 2^{n-k}"

    part (i)
    I know that I need to show that the elements of $C^{\bot}$ are closed, have an identity, an inverse, and are associative (all under addition), but I don't know how to do it though?
    part(ii)
    M is a n \times k matrix of the form \dfrac{A}{I_{k}}. I need to show that  \forall \alpha \in  C^{\bot}, M^{T}.\alpha = 0, but I don't know how to show this or  |C^{\bot}| = 2^{n-k}
    Last edited by HowDoIMath; April 16th 2013 at 08:43 AM.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Junior Member
    Joined
    Apr 2013
    From
    Canada
    Posts
    42
    Thanks
    2

    Re: Help Verifying/Completing Basic Cryptography Proofs

     $h(\alpha,\gamma) \leq p + q$
    should be:
     $h(\alpha,\beta) \leq p + q$
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Basic Set Theory Proofs
    Posted in the Discrete Math Forum
    Replies: 4
    Last Post: December 20th 2011, 09:08 AM
  2. Some basic matrix proofs
    Posted in the Advanced Algebra Forum
    Replies: 4
    Last Post: June 16th 2009, 08:08 PM
  3. Five Properties: basic proofs
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: April 23rd 2009, 06:24 AM
  4. need help with two (basic?) proofs involving equicontinuity
    Posted in the Advanced Math Topics Forum
    Replies: 1
    Last Post: April 18th 2008, 01:26 AM
  5. Integer basic proofs
    Posted in the Number Theory Forum
    Replies: 5
    Last Post: July 22nd 2007, 09:31 AM

Search Tags


/mathhelpforum @mathhelpforum