tag:blogger.com,1999:blog-354419952024-03-13T10:59:14.864-07:00Juaninf BlogNotas de un pseudoprogramadorAnonymoushttp://www.blogger.com/profile/13248249970558720665noreply@blogger.comBlogger57125tag:blogger.com,1999:blog-35441995.post-45644369398933065432016-01-12T11:44:00.000-08:002016-01-12T11:44:17.623-08:00Problem "Marble Toy" Consider the toy shown below. A marble is dropped in at A or B. Levers x, y, and z cause the marble to fall either to the left or right. Whenever a marble encounters a lever, it causes the lever to change state, so that the next marble to encounter the lever will take the opposite branch.<br />
<br />
|A| |B|<br />
| | | |<br />
| x | | y |<br />
/ / \ / / \<br />
/ \ / \<br />
/ /\ \ / /\ \<br />
/ / \ \/ / \ \<br />
/ / \ z / / \ \<br />
\ \ / / \ / /<br />
\ \ / /\ \ / /<br />
\ \/ / \ \/ /<br />
\ / \ /<br />
\ / \ /<br />
| | | |<br />
| | | |<br />
|C| |D|<br />
<br />
<br />
Problem: Describe the set accepted by the DFA.
Solution:
<br />
<br />
<br />
<a href="http://i.stack.imgur.com/F996R.png" imageanchor="1" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" src="http://i.stack.imgur.com/F996R.png" /></a>First the DFA solution is presented in the next table and his diagram in JFLAP in <a href="http://e-connecting.com.br/lncc/hopcroft.jflap">the next file</a>.<br />
<br />
To describe the set accepted by the DFA see that only the half of times that a ball falls in A affects x_2, the same happens for the case B. Then there are three cases to describe the set accepted by the DFA.<br />
<br />
1.-If the word end in B and the numbers of Bs is even (par).<br />
2.-If the word has the form XB where X is formed by As and Bs. The number of Bs on X is even and the half of the numbers of As and Bs is odd (impar) (exactly).<br />
3.-If the word has the form XA where X is formed by As and Bs. The number
of As on X is odd and the half of the numbers of As and Bs is odd.(exactly).Anonymoushttp://www.blogger.com/profile/13248249970558720665noreply@blogger.com0tag:blogger.com,1999:blog-35441995.post-9833462766359625072015-05-15T08:20:00.000-07:002015-10-05T14:00:34.721-07:00Building Simple Chat Client with Parse [Code]I am learning android and I am following the tutorial <a href="https://github.com/codepath/android_guides/wiki/Building-Simple-Chat-Client-with-Parse">Building Simple Chat Client with Parse</a>. I am providing the source code <a href="https://sites.google.com/site/juaninf/simplechat.zip?attredirects=0&d=1">in this link</a>. Here you can find the code for that tutorial. Notice that the data type <span style="background-color: #cccccc;">ParseObject</span> of the variable <span style="background-color: #cccccc;">message</span> in line 76 from the source <span style="background-color: #cccccc;">ChatActivity.java</span> was changed by <span style="background-color: #cccccc;">Message</span>. I do not know why the author of that tutorial creates the object <span style="background-color: #cccccc;">message</span> of the class ParseObject. Case anybody know that, please comment this post.Anonymoushttp://www.blogger.com/profile/13248249970558720665noreply@blogger.com0tag:blogger.com,1999:blog-35441995.post-38933607013030902952014-08-10T09:03:00.000-07:002014-08-26T11:18:15.050-07:00Compuscientia 2014: Cuarta Edición<div class="separator" style="clear: both; text-align: center;">
<a href="http://compuscientia.com/images/1069166_445250812248462_187885000_n.jpg" imageanchor="1" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" src="http://compuscientia.com/images/1069166_445250812248462_187885000_n.jpg" height="200" width="141" /></a></div>
Tenemos el agrado de invitar a la comunidad cientifica y empresarial a presentar trabajos para <a href="http://compuscientia.com/">la cuarta edición de CompuScientia</a>. CompuScientia es una revista de la Sociedad de Estudiantes de Ciencia de la Computación (SECC) que tiene por objetivo conectar a nuestros lectores con la realidad de la Computación en el Perú y el mundo.
En el ámbito académico, se presentan oportunidades para hacer estudios de posgrado en varias universidades alrededor del mundo y muchos estudiantes peruanos han compartido y continuarán compartiendo sus experiencias en CompuScientia. De la misma manera, conferencias y eventos nacionales e internacionales relacionados a la computación merecen ser conocidos y difundidos. Trabajos teóricos, prácticos y aplicados en computación realizados por estudiantes de pregrado, posgrado y otros profesionales también tienen cabida en CompuScientia. En CompuScientia, también hay un gran interés por difundir experiencias académicas y logros de estudiantes y profesionales peruanos y latinoamericanos que son ejemplo para las nuevas generaciones. Análisis de noticias acerca de la realidad de la investigación en el Perú y en el mundo son de interés en CompuScientia. Un caso en el Perú, por ejemplo, es el análisis de la ley universitaria recientemente aprobada.
En el ámbito laboral, startups, experiencias laborales en empresas reconocidas a nivel mundial como Facebook, Google, IBM también merecen ser difundidas. CompuScientia también tiene interés en difundir temas relacionados a la computación tales como: productos creados por jóvenes emprendedores, oportunidades para hacer internships, investigaciones en empresas, patentes y noticias relacionadas al enfoque empresarial.Anonymoushttp://www.blogger.com/profile/13248249970558720665noreply@blogger.com0tag:blogger.com,1999:blog-35441995.post-48570558825087998782014-03-07T03:57:00.001-08:002014-08-20T10:57:32.473-07:00Problema em Teoria dos Códigos<div style="text-align: justify;">
Neste post vou analisar o Problema MINIMUM DISTANCE (MD) (conjeturado NP-Completo em [1] e demostrado NP-Completo em [2]) para poder entender porque o problema computacional associado a este problema é NP-Hard</div>
<div style="text-align: justify;">
<br /></div>
<div style="text-align: justify;">
<b>Problema de Decisão</b> MINIMUM DISTANCE (MD)</div>
<div style="text-align: justify;">
Instancia : Uma matriz binária $H^{m\times n}$ e um $w > 0$.</div>
<div style="text-align: justify;">
Pregunta: Existe algum vector $x\in \mathbb{F}_2^n$ com peso de Hamming $\leq w$ tal que $Hx=0$?<br />
<br />
<div>
<b>Problema de Computación</b> COMPUTATIONAL MINIMUM DISTANCE (CMD)</div>
<div>
Instancia : Uma matriz binária $H^{m\times n}$ e um $w>0$.</div>
<div>
Pregunta: Computar o vector $x\in \mathbb{F}_2^n$, com peso minimo, do código $C$ associado a $H$.</div>
</div>
<div style="text-align: justify;">
<br /></div>
<div style="text-align: justify;">
Veja que este é um problema de decisão porque as resposta possíveis são SIM ou NÃO. Que é NP-Completo esta demostrado em [2]. Que MD seja NP-Completo implica, neste caso, em que COMPUTING MINIMUM DISTANCE (CMD) é NP-Hard. Para demonstrar isto vamos a usar a definição informal que nos da o wikipedia.</div>
<blockquote class="tr_bq">
<span style="background-color: white; font-family: sans-serif; font-size: 12.800000190734863px; line-height: 19.200000762939453px;">Um problema $H$</span><i style="background-color: white; font-family: sans-serif; font-size: 12.800000190734863px; line-height: 19.200000762939453px;"></i><span style="background-color: white; font-family: sans-serif; font-size: 12.800000190734863px; line-height: 19.200000762939453px;"> é NP-difícil se e somente se (</span><a class="mw-redirect" href="http://pt.wikipedia.org/wiki/Sse" style="background-color: white; background-image: none; color: #0b0080; font-family: sans-serif; font-size: 12.800000190734863px; line-height: 19.200000762939453px; text-decoration: none;" title="Sse">sse</a><span style="background-color: white; font-family: sans-serif; font-size: 12.800000190734863px; line-height: 19.200000762939453px;">) existe um problema </span><a href="http://pt.wikipedia.org/wiki/NP-completo" style="background-color: white; background-image: none; color: #0b0080; font-family: sans-serif; font-size: 12.800000190734863px; line-height: 19.200000762939453px; text-decoration: none;" title="NP-completo">NP-completo</a><span style="background-color: white; font-family: sans-serif; font-size: 12.800000190734863px; line-height: 19.200000762939453px;"> L que é </span><a class="new" href="http://pt.wikipedia.org/w/index.php?title=Redu%C3%A7%C3%A3o_em_tempo_polinomial_de_Turing&action=edit&redlink=1" style="background-color: white; background-image: none; color: #a55858; font-family: sans-serif; font-size: 12.800000190734863px; line-height: 19.200000762939453px; text-decoration: none;" title="Redução em tempo polinomial de Turing (página não existe)">Turing-redutível em tempo polinomial</a><span style="background-color: white; font-family: sans-serif; font-size: 12.800000190734863px; line-height: 19.200000762939453px;"> para $H$</span><span style="background-color: white; font-family: sans-serif; font-size: 12.800000190734863px; line-height: 19.200000762939453px;">. Em outras palavras, $</span><i style="background-color: white; font-family: sans-serif; font-size: 12.800000190734863px; line-height: 19.200000762939453px;">L</i><span style="background-color: white; font-family: sans-serif; font-size: 12.800000190734863px; line-height: 19.200000762939453px;"> pode ser resolvido em </span><a class="new" href="http://pt.wikipedia.org/w/index.php?title=Tempo_polinomial&action=edit&redlink=1" style="background-color: white; background-image: none; color: #a55858; font-family: sans-serif; font-size: 12.800000190734863px; line-height: 19.200000762939453px; text-decoration: none;" title="Tempo polinomial (página não existe)">tempo polinomial</a><span style="background-color: white; font-family: sans-serif; font-size: 12.800000190734863px; line-height: 19.200000762939453px;"> por uma</span><a class="new" href="http://pt.wikipedia.org/w/index.php?title=M%C3%A1quina_de_Turing_N%C3%A3o_Determin%C3%ADstica&action=edit&redlink=1" style="background-color: white; background-image: none; color: #a55858; font-family: sans-serif; font-size: 12.800000190734863px; line-height: 19.200000762939453px; text-decoration: none;" title="Máquina de Turing Não Determinística (página não existe)">Máquina de Turing Não Determinística</a><span style="background-color: white; font-family: sans-serif; font-size: 12.800000190734863px; line-height: 19.200000762939453px;"> com um oráculo para </span><i style="background-color: white; font-family: sans-serif; font-size: 12.800000190734863px; line-height: 19.200000762939453px;">H</i><span style="background-color: white; font-family: sans-serif; font-size: 12.800000190734863px; line-height: 19.200000762939453px;">. Informalmente, podemos pensar em um algoritmo que pode chamar tal Máquina de Turing Não-Determinística como uma sub-rotina para resolver </span><i style="background-color: white; font-family: sans-serif; font-size: 12.800000190734863px; line-height: 19.200000762939453px;">H</i><span style="background-color: white; font-family: sans-serif; font-size: 12.800000190734863px; line-height: 19.200000762939453px;">, e resolver </span><i style="background-color: white; font-family: sans-serif; font-size: 12.800000190734863px; line-height: 19.200000762939453px;">L</i><span style="background-color: white; font-family: sans-serif; font-size: 12.800000190734863px; line-height: 19.200000762939453px;"> em tempo polinomial, se a chamada da sub-rotina leva apenas um passo para computar.</span></blockquote>
<div style="text-align: justify;">
Então podemos usar como oraculo um algoritmo que resolve CMD para resolver em tempo polinomial, numa máquina de Turing Não Determinista, o problema MD. Para isto basta só comparar se o $w$ do problema MD é maior ou menor que o resultado retornado pelo oráculo. Se o $w$ fosse maior que o valor retornado pelo oraculo então a resposta do problema MD é SIM. Isto porque se fosse possível calcular a distancia minima do código, digamos $d$, então para qualquer $w\leq d$ a resposta é SIM. Se o $w$ fosse menor que o valor retornado pelo oraculo então a resposta do problema MD é NÃO dado que não pode existir $x$ com peso menor que $d$.</div>
<div style="text-align: justify;">
<br /></div>
<div style="text-align: justify;">
Referências</div>
<div style="text-align: justify;">
[1] Berlekamp, Elwyn R. and McEliece, Robert J. and van Tilborg, Henk C. A. (1978) On the inherent intractability of certain coding problems. IEEE Transactions on Information Theory, 24 (3). pp. 384-386. ISSN 0018-9448.</div>
<div style="text-align: justify;">
[2] The intractability of computing the minimum distance of a code - Vardy - 1997</div>
<br />
<br />Anonymoushttp://www.blogger.com/profile/13248249970558720665noreply@blogger.com0tag:blogger.com,1999:blog-35441995.post-63651291629521989552014-02-04T09:57:00.001-08:002014-02-20T15:10:18.387-08:00Transformação Afim na Criptografia Uma transformação afim é uma transformação entre dois <a href="http://pt.wikipedia.org/wiki/Espa%C3%A7o_afim">espaços afins</a> $A$ e $B$. Essa transformação, ou mapeamento, consiste numa transformação lineal em $A$ somado de um vetor $b \in B$. Ou seja:
$$S(x)=Tx + b.$$
No campo da criptografia post-quântica as transformações afins são usadas para ocultar a chave pública dos sistemas de cifração baseados em multivariados.<br>
<br>
Para os envolvidos na área é de importância saber lidar com as diferentes representações de uma transformação afim. Neste post apresentarei essas representações e mostrarei como converter uma para a outra.
Seja $\mathbb{F}$ um corpo finito com $q$ elementos e $\mathbb{E}$ uma extensão de grau $n$ do corpo $\mathbb{F}$. Seja $S:\mathbb{F}^n\rightarrow \mathbb{F}^n$ uma transformação afim.<br>
<br>
<b>Definição 1:</b> Seja $0\leq i < n$ e $A,B_i \in \mathbb{E}$. Então nós chamamos o polinômio $S(X)=\sum_{i=0}^{n-1}B_i X^{{q}^i}+A$ a representação de uma só variável da transformação afim $S$.<br>
<br>
<b>Definição</b><b> 2: </b>Seja $M_S \in \mathbb{F}^{n\times n}$ uma matriz e $v_s \in \mathbb{F}^n$ um vetor. Então nos chamamos $S(x):=M_Sx+v_s$, a representação matricial da transformação afim $S$ .<br>
<br>
<b>Definição</b> <b>3:</b> Seja o espaço vetorial $\mathbb{F}^n$. Então nós chamamos $\phi:\mathbb{E}\rightarrow \mathbb{F}^n$ com $\phi(a):=b$ e $b_i=a_{i-1}$ de bijeção canônica.<br>
<br>
<b>Teorema:</b> Uma transformação afim, com $v=0$ na representação de uma só variável pode ser transformada eficientemente na sua representação matricial.<br>
<br>
<i>Prova</i>: Definamos $e_i \in \mathbb{F}^n$ com $1\leq i \leq n$, com um $1$ no seu i-th coeficiente e zero no restante. Vamos a mostrar que a coluna $k$ dessa matriz é dada pela seguinte fórmula: $M_k=\phi(S(\phi^{-1}(e_k))).$ Vamos a definir $P(X):=\sum_{i=0}^{n-1}B_i X^{{q}^i}$. Da álgebra conhecemos que o corpo $\mathbb{F}^n$ é também um espaço vetorial sobre o corpo $\mathbb{F}$. Esse espaço vetorial tem a base $V=\{t^0, t^1, t^2,\ldots,t^{{n-1}}\}.$ Vamos a representar os coeficiente de $P(X)$ como $B_i =\sum_{j=0}^{n-1}b_{ij} t^j$ e a variável $X=\sum_{k=0}^{n-1}X_{k}t^k$. Substituindo esses valores em $P(X)$ temos $$P(X) = \sum_{i=0}^{n-1}\sum_{j=0}^{n-1}b_{ij} t^j(\sum_{k=0}^{n-1}X_{k}t^k)^{{q}^i},$$<br>
Usando o <a href="http://en.wikipedia.org/wiki/Binomial_theorem">teorema binomial</a> e reduzindo temos<br>
$$P(X) = \sum_{i=0}^{n-1}\sum_{j=0}^{n-1}b_{ij} \sum_{k=0}^{n-1}X_{k}t^{j+k{{q}^i}},$$<br>
<br>
Escrevendo $t^{j+k{{q}^i}}$ usando a base $V$ temos $t^{j+k{{q}^i}} = \sum_{m=0}^{n-1}c_{ijkm}t^m$. Por tanto:<br>
<br>
$$P(X) = \sum_{i=0}^{n-1}\sum_{j=0}^{n-1}b_{ij} \sum_{k=0}^{n-1}X_{k} \sum_{m=0}^{n-1}c_{ijkm}t^m$$<br>
$$P(X) = \sum_{m=0}^{n-1}\underline{\sum_{i=0}^{n-1}\sum_{j=0}^{n-1}b_{ij} \sum_{k=0}^{n-1}X_{k}c_{ijkm}}_{E}t^m$$<br>
Por outro lado, escrevendo $\phi(S(\phi^{-1}(e_k)))$ usando a base $V$ temos que esta é igual a: $\phi(S(\phi^{-1}(e_k)))=(\sum_{i,j}^{n-1}b_{i,j}c_{ijk0}, \cdots, \sum_{i,j}^{n-1}b_{i,j}c_{ijk(n-1)})$. Por fim, veja que $E_m = (\phi(S(\phi^{-1}(e_1)))[m],\cdots,\phi(S(\phi^{-1}(e_{n-1})))[m])^{T}*(X_1,\cdots, X_{n-1}).$<br>
<br>
No caso de transformação afim com $v \neq 0$ então se tem que v:=$M_k=\phi(S(\phi^{-1}(0)))$ e as colunas de $M$ são $M_k=\phi(S(\phi^{-1}(e_k)))-v.$<br>
<br>
<a href="http://juaninf.blogspot.com/2014/02/tranformacao-afim-mpkc.html#more">leer mas »</a>Anonymoushttp://www.blogger.com/profile/13248249970558720665noreply@blogger.com1tag:blogger.com,1999:blog-35441995.post-2327353027100504632013-12-17T05:04:00.001-08:002013-12-17T05:13:56.786-08:00Algoritmos Randomizados<div style="text-align: center;">
<iframe src="http://www.slideshare.net/slideshow/embed_code/29286062" width="476" height="400" frameborder="0" marginwidth="0" marginheight="0" scrolling="no"></iframe></div>Anonymoushttp://www.blogger.com/profile/13248249970558720665noreply@blogger.com0tag:blogger.com,1999:blog-35441995.post-89154774038010883012013-12-06T07:26:00.001-08:002013-12-06T07:27:10.718-08:00El Faq de las Máquinas de TuringEste post es sólo un oráculo de algunas preguntas frecuentes para quién ya estudió teoria de la computación y con el tiempo ha ido olvidando algunos conceptos.<br />
<div class="separator" style="clear: both; text-align: center;">
<a href="http://www.cs.mun.ca/~kol/courses/6743-f07/descriptive.jpg" imageanchor="1" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" height="320" src="http://www.cs.mun.ca/~kol/courses/6743-f07/descriptive.jpg" width="245" /></a></div>
<br />
Que es una máquina de Turing?<br />
Un Dispositivo<br />
Que es un problema?<br />
Un conjunto de frases de longitud finita que esta asociada a un conjuto de frases también de longitud finita.<br />
Que es un problema decidible?<br />
Un problema que su conjunto asociado solo tiene las frases si y no, es decir existe un método que ya consigue definir esos: si y no. Los problemas decidibles tienen un método definido que consigue decir si el problema(la sentencia) es cierto o falso.<br />
Que es un algoritmo?<br />
No existe un consenso, pero se puede decir que es una máquina de Turing.<br />
Todo método que resuelve un problema decidible puede ser implementado en una máquina de Turing?<br />
no sé. Creo que si.<br />
Que es un problema indecidible?<br />
Un problema para el cual no existe un método tal que sea capaz de resolverlo con una respuesta si o no.<br />
Cuantas programas puedo escribir en una máquina de Turing?<br />
Si es universal muchos, recuerde que una máquina de Turing Universal permite simular cualquier máquina de Turing para cualquier entrada.<br />
Que es PP?<br />
Es la clase de problemas de decisión para los cuáles existe un algoritmo de Montecarlo bilateral que responde si cuando la respuesta correcta es si con probabilidad > 1/2 (idem para no) y el tiempo de ese algoritmo es es un polinómio en el tamaño de la entrada. Otra definición equivalente, es la clase de problemas resolubles por una MT probabilística en tiempo polinomial con probabilidad > 1/2 para todas sus instancias.<br />
NP \in PP?<br />
Si. El problema de la factoración esta en NP, por tanto en PP, entonces existe un algoritmo de montecarlo que consigue factorar como descrito en la pregunta anterior, sólo que máquinas de Turing probabilisticas no existen (en general las no deterministas no existen) y las que se simulan estas no son eficientes, es decir no consiguen factorar en tiempo polinomico.<br />
<br />Anonymoushttp://www.blogger.com/profile/13248249970558720665noreply@blogger.com0tag:blogger.com,1999:blog-35441995.post-41334037427071208202013-07-18T13:37:00.001-07:002013-07-18T13:37:06.926-07:00Compuscientia 2013<div style="background-color: white; color: #777777; font-family: Arial; font-size: 13px; line-height: 1.7em; margin-bottom: 8px; margin-top: 8px; padding: 0px; text-align: justify;">
<a href="http://2.bp.blogspot.com/-tgObeaMwUDc/UehRtACdUyI/AAAAAAAAAXM/sx2lExyq50c/s1600/logocompu.jpg" imageanchor="1" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" src="http://2.bp.blogspot.com/-tgObeaMwUDc/UehRtACdUyI/AAAAAAAAAXM/sx2lExyq50c/s1600/logocompu.jpg" /></a><span style="background-color: transparent; font-size: 10pt; margin: 0px; padding: 0px;">CompuScientia es una revista que busca difundir los diferentes caminos que ofrece el inmenso mundo de la Computación: aplicaciones tecnológicas, áreas de investigación, recomendaciones legales, fuentes de financiamiento de proyectos, oportunidades laborales, entre otros. Siendo así, la revista está dirigida a jóvenes estudiantes de pre y posgrado, profesionales y entusiastas de diferentes carreras de Computación y afines.</span></div>
<div style="background-color: white; color: #777777; font-family: Arial; font-size: 13px; line-height: 1.7em; margin-bottom: 8px; margin-top: 8px; padding: 0px; text-align: justify;">
<span style="background-color: transparent; font-size: 10pt; margin: 0px; padding: 0px;">La Computación y la Tecnología van de la mano, y hoy son dos de los pilares del desarrollo mundial. En consecuencia, CompuScientia tiene el objetivo de presentarlos como agentes importantes para el desarrollo sostenido del país.</span></div>
<div style="background-color: white; color: #777777; font-family: Arial; font-size: 13px; line-height: 1.7em; margin-bottom: 8px; margin-top: 8px; padding: 0px; text-align: justify;">
<span id="internal-source-marker_0.6401110365986824" style="font-family: 'Times New Roman'; font-size: small; margin: 0px; padding: 0px; text-align: start;"><span style="background-color: transparent; font-family: Arial; font-size: 15px; margin: 0px; padding: 0px; vertical-align: baseline;"><span style="font-size: 10pt; margin: 0px; padding: 0px;">CompuScientia es una revista para todos los interesados en conocer más acerca del mundo de la Computación y Tecnología. En CompuScientia les hacemos partícipes de las diversas oportunidades académicas, profesionales y laborales que les pueden interesar.</span></span></span></div>
<div style="background-color: white; color: #777777; font-family: Arial; font-size: 13px; line-height: 1.7em; margin-bottom: 8px; margin-top: 8px; padding: 0px; text-align: justify;">
<span style="font-family: 'Times New Roman'; font-size: small; margin: 0px; padding: 0px; text-align: start;"><span style="background-color: transparent; font-family: Arial; font-size: 15px; margin: 0px; padding: 0px; vertical-align: baseline;"><span style="font-size: 10pt; margin: 0px; padding: 0px;"><br /></span></span></span></div>
<div style="background-color: white; color: #777777; font-family: Arial; font-size: 13px; line-height: 1.7em; margin-bottom: 8px; margin-top: 8px; padding: 0px; text-align: justify;">
<span style="font-family: 'Times New Roman'; font-size: small; margin: 0px; padding: 0px; text-align: start;"><span style="background-color: transparent; font-family: Arial; font-size: 15px; margin: 0px; padding: 0px; vertical-align: baseline;"><span style="font-size: 10pt; margin: 0px; padding: 0px;">Para mas información ingresar a la web <a href="http://www.compuscientia.com/">aquí</a></span></span></span></div>
<div style="background-color: white; color: #777777; font-family: Arial; font-size: 13px; line-height: 1.7em; margin-bottom: 8px; margin-top: 8px; padding: 0px; text-align: justify;">
<span style="font-family: 'Times New Roman'; font-size: small; margin: 0px; padding: 0px; text-align: start;"><span style="background-color: transparent; font-family: Arial; font-size: 15px; margin: 0px; padding: 0px; vertical-align: baseline;"><span style="font-size: 10pt; margin: 0px; padding: 0px;"><br /></span></span></span></div>
<div style="background-color: white; color: #777777; font-family: Arial; font-size: 13px; line-height: 1.7em; margin-bottom: 8px; margin-top: 8px; padding: 0px; text-align: justify;">
<span style="font-family: 'Times New Roman'; font-size: small; margin: 0px; padding: 0px; text-align: start;"><span style="background-color: transparent; font-family: Arial; font-size: 15px; margin: 0px; padding: 0px; vertical-align: baseline;"><span style="font-size: 10pt; margin: 0px; padding: 0px;"><br /></span></span></span></div>
Anonymoushttp://www.blogger.com/profile/13248249970558720665noreply@blogger.com0tag:blogger.com,1999:blog-35441995.post-51331141858487614812013-07-01T09:09:00.000-07:002013-07-01T09:10:34.033-07:00Esquema de Firma Digital Pos Cuántico Lamport-Diffie<div style="text-align: justify;">
<div class="separator" style="clear: both; text-align: center;">
<a href="https://encrypted-tbn2.gstatic.com/images?q=tbn:ANd9GcS7XBn-QkH0H6c3xlk5EvXbEFTHkw6LKNAS6FwqD6XbyGNd95xs5g" imageanchor="1" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" src="https://encrypted-tbn2.gstatic.com/images?q=tbn:ANd9GcS7XBn-QkH0H6c3xlk5EvXbEFTHkw6LKNAS6FwqD6XbyGNd95xs5g" /></a></div>
Este esquema de firma digital fue propuesto en el año de 1979. Es uno de los primeros en ser estudiados dentro de los esquemas de firma digital que se consideran resistentes ataques cuánticos dada su simplicidad para entender. A continuación describiré los algoritmos usados tanto para la generación de llaves como para el proceso de firma y verificación.</div>
<br />
<b>Generación de Llaves:</b><br />
Escoger dos funciones<br />
<ol>
<li>Una función de Mano Única: $$f:\{0,1\}^n \rightarrow \{0,1\}^n$$</li>
<li>Una función Hash $$g:\{0,1\}^{*}\rightarrow \{0,1\}^n$$</li>
</ol>
La llave de firma, X, consiste de $2n$ cadenas de bits de tamaño $n$ elegidas de forma aleatoria uniformemente.<br />
$$X=(x_{n-1}[0], x_{n-1}[1],\cdots,x_0[0],x_0[1])\in \{0,1\}^{n,2n}$$<br />
La llave de verificación, Y, es:<br />
$$Y=(y_{n-1}[0], y_{n-1}[1],\cdots,y_0[0],y_0[1])\in \{0,1\}^{n,2n},$$<br />
donde $$y_i[j] = f(x_i[j]).$$<br />
<br />
<b>Firma:</b><br />
Un documento $$M\in \{0,1\}^{*}$$ es firmado usando la llave X, usando $$d=g(M)=(d_{n-1},\cdots,d_0)$$ como $$\sigma = (x_{n-1}[d_{n-1}],\cdots,x_{0}[d_0])\in \{0,1\}^{n,n}$$<br />
<b>Verificación:</b><br />
Para verificar $\sigma$ el verificador calcula g(M) y verifica si<br />
$$(f(\sigma_{n-1}),\cdots,f(\sigma_0))=(y_{n-1}[d_{n-1}],\cdots,y_0[d_0]).$$<br />
<div style="text-align: justify;">
<br /></div>
<div style="text-align: justify;">
La seguridad de este esquema esta basada en dos nociones de seguridad: resistencia a pre-Imagen que presentan las funciones de mano única y la resistencia a colisiones que presenta una función hash criptográfica. Como ya vimos justamente el esquema Diffie-Lamport usa una función de mano única y una función hash. Funciones hash y funciones de mano única solo admiten ataques genéricos contra las dos nociones de seguridad mencionada. Para ataques contra la noción de resistencia a colisiones, usando un computador clásico, se usa Ataque de Cumpleaños el cual tiene complejidad O(2^{n/2}) de encontrar colisiones con probabilidad 1/2. Para ataques contra la noción de resistencia a pre-imagen, usando un computador clásico, se usa fuerza bruta, la cual en este caso, tiene complejidad de O(2^{n/2}) de encontrar pre-imagen con probabilidad 1/{2^{n/2}}. En el caso de uso de computadores cuánticos para crear ataques contra estas nociones de seguridad lo mejor que se pueda usar es el algoritmo de Groover. Este algoritmo, adaptado para estos ataques, tiene complejidad de O(2^{n/3}) con probabilidad 1/2 de encontrar colisiones y complejidad O(2^{n/3}) de encontrar pre-imágenes con probabilidad 1/{2^{n/3}}, [1,pag 90]. Es por eso que se dice que este esquema de firma digital, con sus limitaciones, es una alternativa para esquemas basados en problemas de la teoría de números como factorización de números grandes y el problema de logaritmo discreto.</div>
<br />
[1] <span style="background-color: white; color: #444444; font-family: arial, sans-serif; font-size: x-small; line-height: 14.545454025268555px;">Johannes; Dahmen, Erik, eds. (2009). </span><span style="background-color: white; color: #444444; font-family: arial, sans-serif; font-size: x-small; font-weight: bold; line-height: 14.545454025268555px;">Post</span><span style="background-color: white; color: #444444; font-family: arial, sans-serif; font-size: x-small; line-height: 14.545454025268555px;">-</span><span style="background-color: white; color: #444444; font-family: arial, sans-serif; font-size: x-small; font-weight: bold; line-height: 14.545454025268555px;">quantum cryptography</span><span style="background-color: white; color: #444444; font-family: arial, sans-serif; font-size: x-small; line-height: 14.545454025268555px;">. </span><span style="background-color: white; color: #444444; font-family: arial, sans-serif; font-size: x-small; font-weight: bold; line-height: 14.545454025268555px;">Springer</span>Anonymoushttp://www.blogger.com/profile/13248249970558720665noreply@blogger.com0tag:blogger.com,1999:blog-35441995.post-88312172048158064822013-04-19T13:00:00.000-07:002013-04-19T13:34:40.799-07:00Ejemplo Criptosistema McEliece en SAGE<div style="text-align: justify;">
En el 1978 McEliece presentó un nuevo criptosistema de clave pública, basado en la Teoría de los Códigos. Dado que esta teoría es muy compleja, los expertos recomiendan una familiarización matemática preliminar con la Teoría de la Codificación, los Códigos de Goppa, y los Cuerpos de Galois.</div>
<div style="text-align: justify;">
En el sistema de McEliece, cada usuario ha de elegir un polinomio irreducible de grado $delta$, y construir una matriz generadora del correspondiente código de Goppa, matriz G, de orden k x n. También ha de calcular la llave pública, que es una matriz generadora del código Goppa. Este código debe ser tal que no exista un algoritmo computable que corrija los errores con éste código en un tiempo pequeño. La llave pública es obtenida a partir de la multiplicación de una matriz aleatoria no singular de orden 2^m-k*m, y una matriz de permutaciones de orden 2^m. Todos los usuarios del sistema mantienen sus respectivas llaves públicas, mientras que las matrices S,G e P serán secretas.</div>
<div style="text-align: justify;">
A continuación presentamos el algoritmo para generación de las llaves, cifrado de un texto plano y descifrado de un texto cifrado, según wikipedia, y su respectiva implementación mediante un ejemplo en SAGE. Es necesario "correr" primero <a href="http://www.blogger.com/blogger.g?blogID=35441995#nombre">la última</a> de las celdas de este post, la cual contiene los algoritmos auxiliares como por ejemplo el <a href="http://juaninf.blogspot.com.br/2011/10/pronto-comparacion-de-algoritmos-para.html">algoritmo de Patterson.</a></div>
<br>
<b>Generación de Llaves</b><br>
<ol>
<li>Alicia selecciona un código de Goppa binario Gamma com parâmetros (n,k) y capacidad de correción de delta errores; </li>
<li>Alicia gera a matriz geradora $G$, de dimensiones n-m*k x n, del código \Gamma;
Selecciona una matriz binaria no singular S, de dimensiones;n-m*k x n-m*k; </li>
<li> Selecciona una matriz de permutación P, de dimensión n; </li>
<li> Computa a matriz $G' = SGP; </li>
<li> La llave pública de Alicia é (G',delta) y su llave privada es (S,G,P).</li></ol><a href="http://juaninf.blogspot.com/2013/04/function-make-div-with-id-mycell-sage.html#more">leer mas »</a>Anonymoushttp://www.blogger.com/profile/13248249970558720665noreply@blogger.com0tag:blogger.com,1999:blog-35441995.post-65399896850117454402013-04-13T12:18:00.002-07:002013-04-13T14:54:00.635-07:00Sistema Demostrablemente Seguro Hace ya algunos dias que estoy queriendo dejar en claro algunos conceptos de seguridad que ya había aprendido y que por el paso del tiempo estaban confusos. Esos conceptos por ejemplo son nociones de seguridad, modelos de ataque, seguridad demostrable etc. Como siempre, lo que entiendo después de la lectura intentó escribirlo como se puede ver en mis entradas <a href="http://juaninf.blogspot.com.br/2013/04/propiedad-de-la-indistinguibilidad-en.html">Propiedad de la Indistinguibilidad en Criptosistemas</a>, <a href="http://juaninf.blogspot.com.br/2013/04/modelo-de-ataque-cca.html">Modelos de Ataque</a>.<br />
<br />
Siguiendo con la recordación, en esta entrada escribo un resumen acerca del concepto sistema demostrablemente seguro (<i>provably secure</i>).<br />
<br />
Dado un criptosistema como podemos probar su seguridad?<br />
<ul>
<li>Tratando de montar un ataque</li>
<ul>
<li>Si el ataque fue encontrado entonces el criptosistema no es seguro.</li>
<li>Si el ataque no fue encontrado no se puede decir nada acerca de la seguridad del criptosistema.</li>
</ul>
<li>Probando que no existe ataque bajo algunas asunciones.</li>
<ul>
<li>Publicar la verificabilidad de la prueba</li>
<li>Ataque encontrado, entonces las asunciones fueron falsas</li>
</ul>
</ul>
<div>
Como hacer esa prueba bajo asunciones?</div>
<div>
<div>
<ul>
<li>Describir un criptosistema y sus modos operacionales,</li>
<li>Formalmente definir la noción de seguridad a lograr = (objetivo que el atacante atacaria + modelo de ataque ). Ejm: IND-CCA2, IND objetivo e CCA2 modelo de ataque.</li>
<li>Realizar asunciones computaciones, (problema factoración, problema logaritmo discreto, dureza de la decodificación de Códigos de Goppa Binário, etc).</li>
<li>Exhibir una reducción entre un algoritmo que rompe la noción de seguridad y uno que rompe la asunción computacional. Ejemplo (RSA is reducible para OW-CCA2(S)).<!-----><!-----></li>
</ul>
<div>
<br /></div>
</div>
</div>
¿Te ha gustado esta entrada? Entonces échame un cable compartiéndola en Twitter. Gracias!
<!-- AddThis Button BEGIN -->
<br />
<div class="addthis_toolbox addthis_default_style ">
<a class="addthis_button_facebook_like" fb:like:layout="button_count" href="http://www.blogger.com/blogger.g?blogID=35441995"></a>
<a class="addthis_button_tweet" href="http://www.blogger.com/blogger.g?blogID=35441995"></a>
<a class="addthis_counter addthis_pill_style" href="http://www.blogger.com/blogger.g?blogID=35441995"></a>
</div>
<script src="http://s7.addthis.com/js/250/addthis_widget.js#pubid=xa-4dcde18b394a19ad" type="text/javascript"></script>
<!-- AddThis Button END -->Anonymoushttp://www.blogger.com/profile/13248249970558720665noreply@blogger.com0tag:blogger.com,1999:blog-35441995.post-23270783914107571872013-04-05T20:26:00.002-07:002013-04-06T06:45:42.212-07:00Propiedad de la Indistinguibilidad en Criptosistemas<div style="text-align: justify;">
<a href="https://encrypted-tbn0.gstatic.com/images?q=tbn:ANd9GcRo4P0O5yeWU09FPiyvbazNEAv0-50PDN82cB8eA00EcqOmiUZeog" imageanchor="1" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" src="https://encrypted-tbn0.gstatic.com/images?q=tbn:ANd9GcRo4P0O5yeWU09FPiyvbazNEAv0-50PDN82cB8eA00EcqOmiUZeog" /></a>Actualmente esta propiedad la poseen la mayoría de criptosistemas. Un criptosistema es denominado seguro en términos de indistinguibilidad si, dado el par de textos planos M0, M1 y el texto cifrado C, no existe atacante que tenga probabilidad mayor al que tendría un atacante con la probabilidad 1/2, para poder afirmar si el texto cifrado C pertenece al cifrado de M0 o M1.<br />
<br /></div>
<div style="text-align: justify;">
<br /></div>
<div style="text-align: justify;">
<b><br /></b></div>
<div style="text-align: justify;">
<b>Indistinguibilidad bajo CPA (IND-CPA):</b></div>
<div style="text-align: justify;">
<b><br /></b></div>
<div style="text-align: justify;">
Para criptosistemas asimétricos esta propiedad es definida como un juego en la que los jugadores son un desafiador y un atacante. El juego consiste en:</div>
<div style="text-align: justify;">
</div>
<ol>
<li>El desafiador crea sus claves publica PK y privada SK;</li>
<li>El atacante puede usar PK para cifrar los mensajes de texto plano que el desee;</li>
<li>El atacante envía para el desafiador los textos planos M0 y M1;</li>
<li>El desafiador elige aleatoriamente uno de los dos mensajes, ME, y lo cifra con el algoritmo de cifración E en C = E(PK, ME);</li>
<li>El atacante es libre de hacer nuevas cifraciones. Finalmente el adversario da su respuesta acerca de si C es E(PK, M0) o E(PK, M1).</li>
</ol>
<div>
<span style="text-align: justify;">Un sistema es dicho IND-CPA seguro si el atacante no tiene una probabilidad notoria de ganar el juego en relación con otro atacante que tenga la probabilidad 1/2 de ganarlo.</span></div>
<div>
<span style="text-align: justify;"><br /></span></div>
<div>
<b>Indistinguibilidad bajo CCA (IND-CCA/IND-CCA2):</b></div>
<div>
<b><br /></b></div>
<div>
Al igual que en la propiedad anterior, esta es definida <span style="text-align: justify;">como un juego en la que los jugadores son un desafiador y un atacante. El juego consiste en:</span></div>
<div>
<ol>
<li>El desafiador crea sus claves publica PK y privada SK;</li>
<li>Dado que el atacante tiene acceso a PK entonces puede hacer cualquier número de cifraciones, así como también puede descifrar texto cifrados usando un oracle de deciframiento.</li>
<li>El atacante envía para el desafiador los textos planos M0 y M1;</li>
<li>El desafiador elige aleatoriamente uno de los dos mensajes, ME, y lo cifra con el algoritmo de cifración E en C = E(PK, ME);</li>
<li>El atacante puede realizar mas cifraciones si lo desea. Si el modelo de ataque del desafiador es:</li>
<ol>
<li>CCA entonces el atacante no puede realizar mas decifraciones de textos cifrados, usando el oracle.</li>
<li>CCA2 entonces el atacante puede realizar mas decifraciones de textos cifrados, usando el oracle, excepto C.</li>
</ol>
<li>Finalmente el adversario da su respuesta acerca de si C es E(PK, M0) o E(PK, M1).</li>
</ol>
</div>
<div style="text-align: justify;">
Un sistema es dicho IND-CCA/CCA2 seguro si el atacante no tiene una probabilidad notoria de ganar el juego en relación con otro atacante que tenga la probabilidad 1/2 de ganarlo.</div>
<div style="text-align: justify;">
<br /></div>
<div style="text-align: justify;">
La indistinguibilidad bajo <a href="http://juaninf.blogspot.com.br/2013/04/modelo-de-ataque-cca.html">CPA</a> (IND-CPA) es una propiedad que la poseen los sistemas denominados probadamente seguros. IND-CPA es equivalente a la propiedad de seguridad semántica en criptosistemas, por lo cual muchas veces esta equivalencia es usado para pruebas criptográficas. Algunos sistemas criptográficos también ofrecen la indistinguibilidad bajo <a href="http://juaninf.blogspot.com.br/2013/04/modelo-de-ataque-cca.html">CCA</a> (IND-CCA).<br />
<br />
La indistinguibilidad contra ataques adaptativos para sistemas criptográficos de llave pública fue introducida por Rackoff and Simon.</div>
<div style="text-align: justify;">
<br /></div>
Anonymoushttp://www.blogger.com/profile/13248249970558720665noreply@blogger.com4tag:blogger.com,1999:blog-35441995.post-13683004268196086592013-04-03T12:44:00.001-07:002013-04-05T20:28:55.179-07:00Modelos de Ataque CPA y CCA<div style="text-align: justify;">
<a href="http://cs-exhibitions.uni-klu.ac.at/uploads/pics/crypt.jpg" imageanchor="1" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" src="http://cs-exhibitions.uni-klu.ac.at/uploads/pics/crypt.jpg" /></a><br />
<b style="font-weight: bold;">Ataque de Texto Plano Escogido.- </b>Es un modelo de ataque que tiene por objetivo descubrir la clave de cifrado de un criptosistema. Consiste en encriptar mensajes planos, por parte del atacante, con el fin de obtener información acerca de la clave usada para cifrar mensajes. En algunos casos el atacante solo necesita encriptar un pedazo del mensaje, para el objetivo descrito anteriormente, este caso es conocido como ataque de inyección de texto plano.<br />
<br />
<b>Ataque de Texto Cifrado Escogido.-</b> Es un modelo de ataque con el objetivo, ambicioso, de obtener la clave de cifrado mediante la habilidad del atacante para engañar al que posee la clave. En este post usaré las siglas en inglés CCA para identificar este tipo de ataque. Para un mejor entendimiento de este tipo de ataque daré un ejemplo simple en un escenario para un criptosistema de llave simétrica:</div>
<div style="text-align: justify;">
<br /></div>
<div style="text-align: justify;">
Supongamos que el general Alfa esta enviando el mensaje cifrado BCFRET al general Beta. El atacante intercepta este mensaje y lo cambia por un mensaje cifrado aleatório FLOULN Cuando el general Beta decifra este mensaje modificado obtiene un mensaje sin sentido AGHPJK Perplejo, llama para el general Alfa y le pregunta porque me ha llegado el mensaje AGHPJK? Acaso han cambiado la clave?. Infelizmente esta llamada también esta siendo interceptada por el atacante, por lo cual el sabe que el mensaje cifrado FLOULN es decifrado en AGHPJK. El utiliza una (de las tantas) forma simple de obtener la llave restando estas dos palabras EEHEBC. En este caso el atacante pudo obtener la llave con tan sólo un mensaje cifrado.<br />
<br />
Se dice que un ataque CCA es no adaptativo si el atacante no usa el texto plano resultante del proceso de engañar al que posee la clave. Y, se dice que el modelo CCA es adaptativo (CCA2) si el atance usa el texto plano resultante del proceso de engañar a quien posee la clave para poder seguir enviando textos<br />
cifrados elegidos. En el ejemplo anterior si Alfa continuara enviando mensajes, después de lo que ocurrió, y usa AGHPJK para crear otro mensaje cifrado aleatório, sería entonces un ejemplo de CCA adaptativo.</div>
<br />
¿Te ha gustado esta entrada? Entonces échame un cable compartiéndola en Twitter. Gracias!
<!-- AddThis Button BEGIN -->
<br />
<div class="addthis_toolbox addthis_default_style ">
<a class="addthis_button_facebook_like" fb:like:layout="button_count" href="http://www.blogger.com/blogger.g?blogID=35441995"></a>
<a class="addthis_button_tweet" href="http://www.blogger.com/blogger.g?blogID=35441995"></a>
<a class="addthis_counter addthis_pill_style" href="http://www.blogger.com/blogger.g?blogID=35441995"></a>
</div>
<script src="http://s7.addthis.com/js/250/addthis_widget.js#pubid=xa-4dcde18b394a19ad" type="text/javascript"></script>
<!-- AddThis Button END -->Anonymoushttp://www.blogger.com/profile/13248249970558720665noreply@blogger.com0tag:blogger.com,1999:blog-35441995.post-62387224361814305022013-03-24T10:19:00.003-07:002013-05-03T14:21:16.951-07:00Torres de Hanoi Implementación [code C++]<div style="text-align: justify;">
<a href="http://upload.wikimedia.org/wikipedia/commons/6/60/Tower_of_Hanoi_4.gif" imageanchor="1" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" src="http://upload.wikimedia.org/wikipedia/commons/6/60/Tower_of_Hanoi_4.gif" /></a>El juego, en su forma más tradicional, consiste en tres varillas verticales. En una de las varillas se apila un número indeterminado de discos (elaborados de madera) que determinará la complejidad de la solución, por regla general se consideran ocho discos. Los discos se apilan sobre una varilla en tamaño decreciente. No hay dos discos iguales, y todos ellos están apilados de mayor a menor radio en una de las varillas, quedando las otras dos varillas vacantes. El juego consiste en pasar todos los discos de la varilla ocupada (es decir la que posee la torre) a una de las otras varillas vacantes. Para realizar este objetivo, es necesario seguir tres simples reglas: </div>
<div style="text-align: justify;">
</div>
<ol>
<li>Sólo se puede mover un disco cada vez. </li>
<li>Un disco de mayor tamaño no puede descansar sobre uno más pequeño que él mismo. </li>
<li>Sólo puedes desplazar el disco que se encuentre arriba en cada varilla. </li>
</ol>
<br />
<div style="text-align: justify;">
[fuente Wikipedia]</div>
<div style="text-align: justify;">
<br /></div>
<div style="text-align: justify;">
A continuación presento una implementación de este juego en C++, usando la estructura pila. </div>
<div style="text-align: justify;">
<br /></div>
<pre class="brush: c">#include <iostream>
#include <stack>
using namespace std;
void hanoi(int, stack<int>&, stack<int>&, stack<int>& );
int main(){
int n;
stack<int> origen;
stack<int> destino;
stack<int> auxiliar;
printf("Ingresa el número de discos:\n");
scanf("%d", &n);</pre>
<pre class="brush: c"> //llenando la pila de origen con los discos
for (int i=0; i<n; i++){
cout<<endl<<n-i<<endl;
origen.push(n-i);
}
hanoi(n, origen, destino, auxiliar);
}
void hanoi(int n, stack<int> &origen, stack<int> &destino, stack<int>& auxiliar){
if (n == 1){
int top = origen.top();
destino.push(top);
origen.pop();
return;
}
else{
//{mover n-1 discos de la torre origen a la torre auxiliar}
hanoi(n-1, origen, auxiliar, destino); //{llamada recursiva}
//Mover un disco de la torre origen a la torre destino
int top = origen.top();
destino.push(top);
origen.pop();
//{mover n-1 discos de la torre auxiliar a la torre destino}
hanoi(n-1, auxiliar, destino, origen); //{llamada recursiva}
}
return;
}
</pre>
Anonymoushttp://www.blogger.com/profile/13248249970558720665noreply@blogger.com2tag:blogger.com,1999:blog-35441995.post-83025582800276533572013-03-13T15:09:00.000-07:002013-03-13T15:09:16.265-07:00Representación de qbits en la esfera de BlochUn qubit o cubit (del inglés quantum bit, bit cuántico) es un sistema cuántico con dos estados propios y que puede ser manipulado arbitrariamente. A seguir desarrollaré un ejercicio que trata acerca de la representación de qbits en la <a href="http://es.wikipedia.org/wiki/Qubit#Esfera_de_Bloch">esfera Bloch</a>. Para este propósito usaré una <a href="http://www.ece.uc.edu/~mcahay/blochsphere/index.html">herramienta</a> para hacer los gráficos respectivos.<br />
<br />
<b>Encontrar la posición del siguiente vector: </b><br />
<b>$$|+\rangle = \dfrac{|0\rangle + |1\rangle}{\sqrt[]{2}},$$</b><br />
<b>en la esfera de Bloch.</b><br />
<br />
Usando la reducción $$\alpha|0\rangle + \beta|1\rangle = e^{i\alpha}(\cos \dfrac{\theta}{2}|0\rangle+e^{i\phi}\sin \dfrac{\theta}{2}|1\rangle).$$ Llevando en consideración que $$e^{i\alpha}$$ es una fase global y haciendo $$j = \sqrt[]{-1}$$ tenemos:$$|+\rangle = \dfrac{|0\rangle + |1\rangle}{\sqrt[]{2}}= \dfrac{|0\rangle}{\sqrt[]{2}}+ \dfrac{|1\rangle}{\sqrt[]{2}}= \alpha|0\rangle + \beta|1\rangle = e^{i\alpha}(\cos \dfrac{\theta}{2}|0\rangle+e^{i\phi}\sin \dfrac{\theta}{2}|1\rangle)$$ $$\alpha = \dfrac{1}{\sqrt[]{2}}= \cos \dfrac{\theta}{2}$$ y<br />
<br />
$$\beta = \dfrac{1}{\sqrt[]{2}}= e^{i\phi}\sin \dfrac{\theta}{2},$$ luego $$\theta = \pi/2\,\,\,,\phi = 0$$ A seguir mostramos el respectivo gráfico para esos valores de <span style="background-color: white; font-size: 13px; text-align: -webkit-center;">θ y φ</span><br />
<br />
<div class="separator" style="clear: both; text-align: center;">
<a href="http://2.bp.blogspot.com/-i-KZMwjj5uw/UUD3R9RQeHI/AAAAAAAAAVw/5qCCYchNndk/s1600/teta90phi0.png" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" height="320" src="http://2.bp.blogspot.com/-i-KZMwjj5uw/UUD3R9RQeHI/AAAAAAAAAVw/5qCCYchNndk/s320/teta90phi0.png" width="241" /></a></div>
<br />
<br />
<br />Anonymoushttp://www.blogger.com/profile/13248249970558720665noreply@blogger.com0tag:blogger.com,1999:blog-35441995.post-56664623042635188612013-03-06T05:29:00.000-08:002014-03-06T06:19:12.697-08:00Livraria LibMC<h2>
<b>Introdução</b></h2>
<br />
<div style="text-align: justify;">
Dentro dos sistemas criptográficos de chave pública existem alguns que, atualmente, têm se destacado devido ao fato de, aparentemente, resistirem aos ataques que são provenientes do uso dos computadores quânticos, formando, assim, uma família denominada de <i>post-quantum cryptosystems</i>. Estes sistemas criptográficos, em sua grande maioria, têm suporte matemático nos códigos códigos de Goppa binário, como apresentado por McEliece e Niederreiter. Neste post, apresento uma livraria para implementar os algoritmos de decodificação algébrica para códigos de Goppa binário com parâmetros $[n,k,d]$ suficientemente grandes. Para conseguir isto, desenvolvemos uma implementação híbrida, usando o CAS(<i>computer algebra system</i>) SAGE para os algoritmos de decodificação e algumas funções modificadas do software <a href="http://www-rocq.inria.fr/secret/CBCrypto/index.php?pg=hymes">HyMES</a> (feito em C) para a geração do polinômio síndrome (de forma randômica), que é uma das entradas para os algoritmos de decodificação. Caso a livraria não fosse usado para gerar o polinômio síndrome, randomicamente, a implementação apenas no SAGE ficaria, obviamente, muito limitada em tempo de decodificação, devido ao carácter simbólico do mesmo. </div>
<br />
<h2>
Como usar</h2>
<div>
A livraria esta feita para ser usada em SAGE versão para 32 bits. Para instalar a livraria segue os passos:</div>
<div>
<ol>
<li>Descarregar de <a href="https://sites.google.com/site/juaninf/randomGoppa.so.zip?attredirects=0&d=1">aqui</a>.</li>
<li>Descomprimir o arquivo <i>zipeado</i>.</li>
<li>Copiar o arquivo na pasta: <i>local/lib/python/site-packages.</i></li>
<li>Reiniciar o SAGE.</li>
</ol>
<div>
Exemplo de uso<br />
<div class="compute1">
<script type="text/x-sage">
from randomGoppa import *
m = 4; n = 2^m-1; debug = 1
delta = 2; # numero de errors que pode corregir
vari = py_generatorParity(m,n,delta,debug,1)
#Não pressionar o botão Evaluate. Esta livraria, que esta na etapa experimental, no esta instalada nos servidores de SAGE
</script>
</div>
</div>
</div>
<div>
<br />
Veja que as entradas do gerador são: $m$ é o grau do polinômio $p(X)$ tal que $F = K/p(X)$, com $K = \mathbb{F}$$_2$, $n$ é o comprimento de cada palavra chave e delta é o grau do polinômio de Goppa. As saídas são: o Polinômio de Goppa, a matriz de teste de paridade do código gerado e o vetor codificado, ou seja $mG+e$.<br />
<br />
Este trabalho foi desenvolvido no LNCC, sendo meus orientadores Renato Portugal e Nolmar Melo.</div>
<div>
<br /></div>
<br />Anonymoushttp://www.blogger.com/profile/13248249970558720665noreply@blogger.com0tag:blogger.com,1999:blog-35441995.post-2673808024134670192013-02-24T18:52:00.001-08:002013-03-01T02:02:01.178-08:00Solución para String como Nombre de Clase en C++ [code]El problema es como usar una variable de tipo string (char*) de tal forma que podamos crear instancias de una clase que tenga el nombre de la variable string. Aqui les presento una solución:<br />
<br />
Supongamos dos clases Gauss y Patterson:<br />
<br />
<pre class="brush: c">
class Gauss {
public:
Gauss() { std::cout << "Object of class Gauss created\n"; }
static void * create() { return (void*) new Gauss; }
}
class Patterson {
public:
Patterson() { std::cout << "Object of class Patterson created\n"; }
static void * create() { return (void*) new Patterson; }
}
</pre>
Definiremos un nuevo tipo de dato, vacío.
<br />
<pre class="brush: c">typedef void * (*ptr)();
</pre>
Ahora el ejemplo
<br />
<pre class="brush: c">int main() {
std::map<std::string, fptr> fpmap;
//Insertamos los pares nombre de clase y tipo de dato de la clase
fpmap.insert(std::make_pair(std::string("Gaus"), Gauss::create));
fpmap.insert(std::make_pair(std::string("Patterson"), Patterson::create));
//Obteniendo un objeto del Tipo Patterson
void * obj = fpmap["Patterson"]();
}</pre>
¿Te ha gustado esta entrada? Entonces échame un cable compartiéndola en Twitter. Gracias!
<!-- AddThis Button BEGIN -->
<br />
<div class="addthis_toolbox addthis_default_style ">
<a class="addthis_button_facebook_like" fb:like:layout="button_count" href="http://www.blogger.com/blogger.g?blogID=35441995"></a>
<a class="addthis_button_tweet" href="http://www.blogger.com/blogger.g?blogID=35441995"></a>
<a class="addthis_counter addthis_pill_style" href="http://www.blogger.com/blogger.g?blogID=35441995"></a>
</div>
<script src="http://s7.addthis.com/js/250/addthis_widget.js#pubid=xa-4dcde18b394a19ad" type="text/javascript"></script>
<!-- AddThis Button END -->Anonymoushttp://www.blogger.com/profile/13248249970558720665noreply@blogger.com0tag:blogger.com,1999:blog-35441995.post-64548889055061735192013-02-17T17:40:00.001-08:002013-02-26T13:53:59.803-08:00Configuración de ECUT en Eclipse + Tutorial<a href="https://encrypted-tbn2.gstatic.com/images?q=tbn:ANd9GcQOmB0zFgweL44eYcuTNH4OUH4JoLegys7CFhkv8VjpCMf1SYfZWAD5LE8" imageanchor="1" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" src="https://encrypted-tbn2.gstatic.com/images?q=tbn:ANd9GcQOmB0zFgweL44eYcuTNH4OUH4JoLegys7CFhkv8VjpCMf1SYfZWAD5LE8"></a><span style="background-color: white; color: #555555; font-family: sans-serif; font-size: 13px; line-height: 18px;">El<a href="http://sourceforge.net/projects/ecut/"> proyecto ECUT</a> (Eclipse C++ <i>Unit Testing</i>) integra CppUnit dentro de Eclipse C/C++. El objetivo de ECUT es proveer un conjunto de bibliotecas que son usadas en programación para hacer pruebas unitarias en alguna aplicación software hecha en C++. Este conjunto de bibliotecas realiza una tarea similar a la que hace JUnit para aplicaciones hechas en Java.</span><br>
<span style="background-color: white; color: #555555; font-family: sans-serif; font-size: 13px; line-height: 18px;"><br></span>
<span style="background-color: white; color: #555555; font-family: sans-serif; font-size: 13px; line-height: 18px;"><br></span>
<span style="background-color: white; color: #555555; font-family: sans-serif; font-size: 13px; line-height: 18px;">En este post indicaré los pasos necesarios para configurar ECUT en Eclipse Indigo, bajo el sistema operativo Ubuntu 12.04. Así mismo se presenta un video con un tutorial acerca de este framework.</span><br>
<a href="http://juaninf.blogspot.com/2013/02/configuracion-de-ecut-en-eclipse.html#more">leer mas »</a>Anonymoushttp://www.blogger.com/profile/13248249970558720665noreply@blogger.com0tag:blogger.com,1999:blog-35441995.post-30684231891499667262013-02-02T06:43:00.002-08:002013-03-20T07:12:23.053-07:00Teoria de Filtrado y Procesamiento de Imágenes<div style="text-align: justify;">
<span style="background-color: white; color: #222222; font-family: arial, sans-serif; font-size: x-small; line-height: 14.545454025268555px; text-align: left;">¿</span>Como desarrollar una teoria para filtrado linear (filtros pasa-alta, pasa-baixa e pasa-banda) usando la transformada discreta de Fourier?<br>
A continuación desarrollaré una teoría que responde a esta pregunta fundamentada en [1]. Para desarrollar la teoría necesitamos entender el significado de alta y baja frecuencia en imágenes. Necesitamos entender, también, que son máscaras para hacer convolución, cuantos tipos de convolución se tienen, así como, cuando usamos uno u otro tipo de convolución.</div>
<br>
<div style="text-align: justify;">
<b>Alta Frecuencia en imágenes:</b> Se dice que una imagen presenta alta frecuencia, en el dominio de Fourier, si tiene valores grandes en los componentes de alta frecuencia, es decir, los datos están cambiando rápidamente en una escala de distancia corta, por ejemplo una página de texto. Otro ejemplo es el ruido, el cual es generalmente considerado como alta frecuencia, así un filtrado de paso bajo puede ser utilizado para la reducción del ruido.</div>
<br>
<div style="text-align: justify;">
<b>Baja Frecuencia en imágenes</b>: Se dice que una imagen tiene baja frecuencia si sus valores son pequeños en los componentes de baja frecuencia, es decir, la imagen contiene objetos que ocupan gran parte de ella sin cambiar bruscamente de intensidad. Por ejemplo un único objeto bastante simple, que ocupa la mayor parte de la imagen.</div>
<br>
<a href="http://juaninf.blogspot.com/2013/02/teoria-de-filtrado-y-procesamiento-de.html#more">leer mas »</a>Anonymoushttp://www.blogger.com/profile/13248249970558720665noreply@blogger.com0tag:blogger.com,1999:blog-35441995.post-86993347229850651872013-01-30T14:42:00.001-08:002013-02-24T16:33:04.568-08:00Creando un Filtro de Pasa Banda con Gaussianas con MAPLEEn este post desarrollaré un ejercicio que trata acerca de la "creación" de un <b>Filtro de Pasa Banda</b> usando Gausianas. Una Gausiana esta definida como:
$$G_{\alpha} = \frac{1}{2\sqrt[]{\pi \alpha}}\exp(-\frac{x^2}{4\alpha})$$
donde $$\alpha > 0.$$ Pues bien, vamos a definir nuestro filtro de pasa banda como:
$$h(x)=G_{\alpha}(x) + G_{\beta}(x).$$
Para poder ver experimentalmente que el filtro definido arriba es de pasa banda tendríamos aplicar la propiedad de modulación en cada Gaussiana, quedando la expresión arriba en el dominio de Fourier de la siguiente forma:
$$h(x)=G_{\alpha}(x)\exp (j w_0 x) + G_{\beta}(x)\exp (j w_1 x).$$
$$\iff$$
$$H(w) = \exp(-\alpha(w-w_0)^2) + \exp(-\beta(w-w_1)^2)$$
Haciendo ω_0 = 2 y ω_1 = -2
Graficaremos en MAPLE el filtro de pasa banda definido por H(ω):
Dando los valores de α y β tenemos:<br>
<a href="http://juaninf.blogspot.com/2013/01/creando-un-filtro-de-pasa-banda-con.html#more">leer mas »</a>Anonymoushttp://www.blogger.com/profile/13248249970558720665noreply@blogger.com0tag:blogger.com,1999:blog-35441995.post-83786561250041288952013-01-28T19:20:00.004-08:002013-02-24T14:19:38.306-08:00Teorema de la Convolución CircularEn el <a href="http://juaninf.blogspot.com.br/"><i><b>post anterior había</b></i></a> comentado acerca de la propiedad de dezplazamiento circular de las señales contínuas. Pues bien, en este nuevo post haré uso de esa propiedad para demostrar (según [1]) de manera similar el Teorema de la Convolución Circular. <br>
<div class="separator" style="clear: both; text-align: center;">
<a href="http://cnx.org/content/m12831/latest/cconv_s1.png" imageanchor="1" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" height="100" src="http://cnx.org/content/m12831/latest/cconv_s1.png" width="122"></a></div>
<b>Teorema 1:</b>
A DFT de la convolución circular de dos secuencias es igual al producto de las DFTs de las sequencias. Es decir si
$$x[n]=\sum_{m=0}^{N-1}v[n-m]_c u[m]$$
entonces
$$DFT\left\{{x[n]}\right\}=DFT\left\{{v[n]}\right\}DFT\left\{{u[n]}\right\}.$$
<b>Demostración:</b>
$$DFT\left\{{x[n]}\right\}=\sum_{n=0}^{N-1}x[n]\exp(\frac{-2 j \pi k n}{N})$$
<br>
<a href="http://juaninf.blogspot.com/2013/01/teorema-de-la-convolucion-circular.html#more">leer mas »</a>Anonymoushttp://www.blogger.com/profile/13248249970558720665noreply@blogger.com0tag:blogger.com,1999:blog-35441995.post-58677857307613103932012-12-17T17:29:00.000-08:002013-02-24T16:33:37.932-08:00Desplazamiento CircularEn el campo del procesamiento de señales pocas veces había escuchado acerca de la convolución circular. Es por eso que en esta, y otra, entrada me encargaré de definir matemáticamente la convolución circular y algunas de sus propiedades en señales discretas.
<br>
Para esto primero definimos el $l-$<i>shift</i> circular de una secuencia $u[n]$ como $u[n-l \mod N]=u[n-l]_c$, en la figura a continuación podemos apreciar un ejemplo para $l=2,N=5$<br>
<a href="http://juaninf.blogspot.com/2012/12/convolucion-circular.html#more">leer mas »</a>Anonymoushttp://www.blogger.com/profile/13248249970558720665noreply@blogger.com0tag:blogger.com,1999:blog-35441995.post-80842433571418046642012-07-09T08:42:00.001-07:002013-02-24T16:34:42.027-08:00Problema con instalación de opencv en UbuntuHola a todos,
hace ya unos dias estaba intentando instalar opencv en Ubuntu Release 12.04 (precise) 64-bit siguiendo los pasos presentados en este tutorial "<a href="http://opencv.willowgarage.com/wiki/InstallGuide_Linux">http://opencv.willowgarage.com/wiki/InstallGuide_Linux</a>". Al escribir make en la linea de comandos obtenia el siguiente mensaje "No rule to make target libbz2.so". Bien, la solución para este problema es copiar este archivo "/lib/x86_64-linux-gnu/libbz2.so" en "/usr/lib" y luego hacer make otra vez.
Espero este "tip" pueda ayudarles a seguir con otros pendientes.
<br>
¿Te ha gustado esta entrada? Entonces échame un cable compartiéndola en Twitter. Gracias!
<!-- AddThis Button BEGIN -->
<div class="addthis_toolbox addthis_default_style ">
<a class="addthis_button_facebook_like" fb:like:layout="button_count"></a>
<a class="addthis_button_tweet"></a>
<a class="addthis_counter addthis_pill_style"></a>
</div>
<script type="text/javascript" src="http://s7.addthis.com/js/250/addthis_widget.js#pubid=xa-4dcde18b394a19ad"></script>
<!-- AddThis Button END -->Anonymoushttp://www.blogger.com/profile/13248249970558720665noreply@blogger.com0tag:blogger.com,1999:blog-35441995.post-41122615666772015132011-10-10T10:30:00.000-07:002013-02-24T19:40:15.218-08:00Algoritmo para Decodificação de Códigos de Goppa Binário<br />
<div style="text-align: justify;">
<div class="separator" style="clear: both; text-align: center;">
<a href="http://3.bp.blogspot.com/-lt6-zIo9Fog/TZcycj8giJI/AAAAAAAAATs/IRUX9NxpKqs/s1600/criptografia.jpg" imageanchor="1" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" height="220" src="http://3.bp.blogspot.com/-lt6-zIo9Fog/TZcycj8giJI/AAAAAAAAATs/IRUX9NxpKqs/s320/criptografia.jpg" width="188" /></a></div>
Dentre os sistemas criptográficos assimétricos ou de chave pública práticos, eficientes e seguros temos: DSA, RSA, baseados em curvas Elípticas, entre outros. A segurança desses sistemas está ameaçada devido ao advento da computação quântica e do algoritmo quântico desenvolvido por Peter Shor em 1994, que resolve o problema da fatoração de números inteiros em tempo polinomial.</div>
<div style="text-align: justify;">
Em 1978 Robert McEliece propôs um sistema criptográfico aleatório que, na época, não foi posto em prática devido ao fato do tamanho de suas chaves serem consideravelmente grandes. Atualmente esse sistema tem tido muita aceitação por parte da comunidade de pesquisadores em criptografia devido à sua resistência aos ataques provenientes dos algoritmos quânticos, como o algoritmo o de Shor. Outra vantagem deste sistema criptográfico é o fato de que seus algoritmos de cifração e decifração são mais rápidos, no que se refere à complexidade de tempo, em comparação com o sistema consolidado RSA.</div>
<div style="text-align: justify;">
<br /></div>
<div style="text-align: justify;">
Este post está focado na implementação do algoritmo de decodificação para códigos de Goppa [1]. Para isto, apresentarei, embaixo, esta implementação feita no <a href="http://www.sagemath.org/">CAS SAGE</a>. Note que o código escrito ali pode ser "rodado" fazendo click no botão Evaluate.</div>
<br />
<br />
<h2>
Implementação do Algoritmo do Patterson</h2>
<br />
<div class="compute">
<script type="text/x-sage">
#Algoritmos Auxiliares
def split(p):
# split polynomial p over F into even part po
# and odd part p1 such that p(z) = p2 (z) + z p2 (z)
Phi1 = p.parent()
p0 = Phi1([sqrt(c) for c in p.list()[0::2]])
p1 = Phi1([sqrt(c) for c in p.list()[1::2]])
return (p0,p1)
def xgcdm1(self, other):
delta = self.degree()
if other.is_zero():
R = self.parent()
return self, R.one_element(), R.zero_element()
# Algorithm 3.2.2 of Cohen, GTM 138
R = self.parent()
A = self
B = other
U = R.one_element()
G = A
V1 = R.zero_element()
V3 = B
while true:
Q,R = G.quo_rem(V3)
T = U - V1*Q
U = V1
G = V3
V1 = T
V3 = R
if V3.degree() <= floor((delta-1)/2) and G.degree() <= floor((delta)/2):
#if V3.degree() < floor((delta-1)/2):# or Q.degree() < floor((delta-1)/2):#(delta-2)/2)):# or V3 == 0:
break
V = (G-A*U)//B
lc = G.leading_coefficient()
return G/lc, U/lc, V/lc
def g_inverse(p,g):
(d,u,v) = xgcd(p,g)
return u.mod(g)
#Implementação do algoritmo de Patterson
def decodePatterson(y):
s2 = H*y
s2 = vector(s2)
print 's2',s2
X1 = X;
g1 = g
polSyn1 = PR(0);
for i in range(len(s2)):
polSyn1 = polSyn1 + s2[i]*(X1^(len(s2)-i-1))
g0g1 = split(g1);
w = ((g0g1[0])*g_inverse(g0g1[1],g1)).mod(g1)
T0T1 = split(g_inverse(polSyn1,g1) + X1)
R = (T0T1[0]+(w)*(T0T1[1])).mod(g1)
(a11,b11,c11) = xgcdm1(g1,R);
sigma = a11^2+X1*(c11^2)
for i in range(N):
if (sigma(a^i)==0): # an error occured
print 'error position',i
m = 4; K = GF(2); F.<a> = GF(2^m); delta = 3
PR = PolynomialRing(F,'X')
X = PR.gen()
N = 15
L = [a^i for i in range(N)]
g = X^3 + X + 1
print 'polinômio de Goppa'
print g
T = matrix(F,delta,delta)
for i in range(delta):
count = delta - i + 1 - 1
for j in range(delta):
if i > j:
T[i,j]=g.list()[count]
count = count + 1
if i < j:
T[i,j] = 0
if i == j:
T[i,j] = 1
V = matrix([[L[j]^i for j in range(N)] for i in range(delta)])
D = diagonal_matrix([1/g(L[i]) for i in range(N)])
H = T*V*D
#print H #descomentar para olhar a matrix de teste de paridade em GF(2^m)
H_Goppa_K = matrix(K, m*H.nrows(), H.ncols())
for i in range (H.nrows()):
for j in range(H.ncols()):
be = bin(eval(H[i,j].int_repr()))[2:]
be = '0'*(m-len(be))+be; be = list(be)
H_Goppa_K[m*i:m*(i+1),j]=vector(map(int,be))
print 'matrix de teste de paridade'
print H_Goppa_K
krnl = H_Goppa_K.right_kernel();
G_Goppa = krnl.basis_matrix();
print 'matrix geradora'
print G_Goppa #descomentar para olhar a matrix geradora
#Caso de prova
u = vector(K,[randint(0,1) for _ in range(G_Goppa.nrows())])
print 'vetor a codificar'
print u
c = u*G_Goppa
print 'vetor codificado'
print c
e = vector(K,N)
#Suponhamos que ao vetor c é adicionado erros nas posições 2 e 3
e[2] = 1
e[3] = 1
print 'vetor erro'
print e
y = c + e
print 'vetor c com erro'
print y
print 'decodificando'
decodePatterson(y)
</script></div>
[1] N.J Patterson, ``The Algebraic Decoding of Goppa Codes", { IEEE Transactions on Information Theory}, IT-21(2):203-207, 1974.
¿Te ha gustado esta entrada? Entonces échame un cable compartiéndola en Twitter. Gracias!
<!-- AddThis Button BEGIN -->
<br />
<div class="addthis_toolbox addthis_default_style ">
<a class="addthis_button_facebook_like" fb:like:layout="button_count" href=""></a>
<a class="addthis_button_tweet" href=""></a>
<a class="addthis_counter addthis_pill_style" href=""></a>
</div>
<script src="http://s7.addthis.com/js/250/addthis_widget.js#pubid=xa-4dcde18b394a19ad" type="text/javascript"></script>
<!-- AddThis Button END -->Anonymoushttp://www.blogger.com/profile/13248249970558720665noreply@blogger.com4tag:blogger.com,1999:blog-35441995.post-67407795254717346162011-06-25T11:36:00.000-07:002011-06-25T15:28:44.782-07:00Overflow en FortranBuenas tardes, <br /><br />Ayudando a un amigo a correr su programa en fortran ocurría el siguiente error<br /><span style="font-style:italic;"><span style="font-weight:bold;">additional relocation overflows omitted from the output</span></span>, al compilar con gfortran su programa, fue así que investigando, encontramos esta forma de compilar para solucionar el problema<br /><br />gfortran <span style="font-weight:bold;">-fpic</span> h.f -o eje<br /><br />espero les sea de utilidad ...Anonymoushttp://www.blogger.com/profile/13248249970558720665noreply@blogger.com0