Return to reliable.tex CVS log

Up to [local] / OpenXM / doc / calc2000p

Annotation of OpenXM/doc/calc2000p/reliable.tex, Revision 1.1

1.1     ! noro        1: % $OpenXM$
        !             2: \documentclass{slides}
        !             3: \usepackage{color}
        !             4: \usepackage{rgb}
        !             5: %{\color{red} Asir}
        !             6: \begin{document}
        !             7: \parskip 5pt
        !             8: \fbox{{\huge \color{blue} We Are Reliable}}
        !             9:
        !            10: {\color{red} Compute GB on a client $\Rightarrow$ Verify it on a server}
        !            11:
        !            12: {\color{red} $\{g_i\}$ is a GB of $\{f_j\}$}
        !            13: $\Leftrightarrow$ $\{g_i\}$ is a GB (trivial)\\
        !            14: and {\color{green} $\{g_i\}$ is generated by $\{f_j\}$ (non trivial)}.
        !            15:
        !            16: \vskip 10pt
        !            17:
        !            18: {\color{red} Check of the generation}\\
        !            19: Find {\color{turquoise} polynomials} $c_j$ s.t.$g_i = \sum c_jf_j$ : {\color{red} hard}.
        !            20:
        !            21: {\color{orange} Alternatively}
        !            22:
        !            23: $\{h_k\}$ : intermediate bases ($\{f_j\}, \{g_i\}\subset \{h_k\}$)\\
        !            24: Find {\color{turquoise} monomials} $m_l$ s.t. $h_k = \displaystyle{\sum_{l<k} m_l h_l}$ : {\color{SeaGreen} trivial}.
        !            25:
        !            26: \medbreak
        !            27:
        !            28: \begin{tabbing}
        !            29: {\color{red} Verification}\\
        !            30: After each normal form computation,\\
        !            31: {\color{green} Client} \=: \= sends a list $\{h,\{l_1,m_1\},\ldots,\{l_s,m_s\}\}$.\\
        !            32: \>\>where $h$ is the normal form.\\
        !            33: {\color{green} Server}  \>: \> checks whether  $h=\sum m_k h_{l_k}$, then\\
        !            34: \>\> registers $h$ as a new basis element.
        !            35: \end{tabbing}
        !            36:
        !            37: \medbreak
        !            38:
        !            39: {\color{red} Implementation of the verifier} : {\color{SeaGreen}easy}\\
        !            40: \quad It requres only polynomial arithmetics.
        !            41:
        !            42: {\color{red} Reliability} : {\color{SeaGreen} higher than simple double check}
        !            43: \vskip 20pt
        !            44: \rightline{ {\color{red} {\tt http://www.openxm.org} }}
        !            45: \end{document}