分类： algorithm

TOTP算法
TOTP 是 Time-based One Time Password 的缩写，可以翻译为基于时间的一次性密码，由于其算法过程简单，安全性高，实施成本低，在各种系统的身份认证中，经常用来辅助认证，这种认证方式通常被叫做两步验证 或2FA 或 MFA ，严格地讲，TOTP是MFA(多因子认证)的一种实现。

在一些对安全性要求较高的网站，通常会提供2FA验证选项，登录时除了需要输入密码，还需要验证动态密码，这样即使密码泄露，还有一道防线保障账户安全。比如阿里云，腾讯云均支持开启MFA验证。

动态密码的生成，需要双方基于相同的授时系统，系统生成的密钥，双方都需要保存，密码算法是公开的，验证时不需要传递密钥，只需要传递密码。

开启两步验证可以使用Authy，Google Authenticator，Microsoft Authenticator 等软件，密钥需要妥善保存，密码变化默认频率是30秒，这个步长参数可以根据业务特性修改，由于双方时间往往会有些许差异，所以密码产生通常有一个倒计时，如果密码发送前已经发生变化，可能出现验证失败，服务端考虑到时延，也会有一定的容错机制。

如果使用Linux系统，也有很多现成类库可供使用，例如开源项目pyotp

https://github.com/pyauth/pyotp

执行 pip3 install pyotp 后，使用下面的代码就可以生成密码。
```
import pyotp
print(pyotp.TOTP('密钥').now())
```
TOTP算法文档收录在rfc6238

https://tools.ietf.org/html/rfc6238
2021-02-07

斐波那契数列算法

递归算法示例：
Python

def Fibonacci(n):
    if  n==0:
        return 0
    if  n==1:
        return 1
    else:
        return Fibonacci(n-1) + Fibonacci(n-2)
print(Fibonacci(7))

PHP

<?php
function Fibonacci($n)
 {
    if ( $n == 0) return 0;
    if ( $n == 1) return 1;
    return Fibonacci($n-1) + Fibonacci($n-2);
 }
echo Fibonacci(10);

非递归实现：

Python

def Fibonacci(n):
    a,b = 1,1
    for i in range(n-1):
        a,b = b,a+b
    return a
print(Fibonacci(8))

2015-05-12

使用PHP计算约瑟夫问题
约瑟夫问题（有时也称为约瑟夫斯置换，是一个出现在计算机科学和数学中的问题。在计算机编程的算法中，类似问题又称为约瑟夫环。又称“丢手绢问题”.）

据说著名犹太历史学家 Josephus有过以下的故事：在罗马人占领乔塔帕特后，39 个犹太人与Josephus及他的朋友躲到一个洞中，39个犹太人决定宁愿死也不要被敌人抓到，于是决定了一个自杀方式，41个人排成一个圆圈，由第1个人开始报数，每报数到第3人该人就必须自杀，然后再由下一个重新报数，直到所有人都自杀身亡为止。然而Josephus 和他的朋友并不想遵从。首先从一个人开始，越过k-2个人（因为第一个人已经被越过），并杀掉第k个人。接着，再越过k-1个人，并杀掉第k个人。这个过程沿着圆圈一直进行，直到最终只剩下一个人留下，这个人就可以继续活着。问题是，给定了和，一开始要站在什么地方才能避免被处决？Josephus要他的朋友先假装遵从，他将朋友与自己安排在第16个与第31个位置，于是逃过了这场死亡游戏。[1]
17世纪的法国数学家加斯帕在《数目的游戏问题》中讲了这样一个故事：15个教徒和15 个非教徒在深海上遇险，必须将一半的人投入海中，其余的人才能幸免于难，于是想了一个办法：30个人围成一圆圈，从第一个人开始依次报数，每数到第九个人就将他扔入大海，如此循环进行直到仅余15个人为止。问怎样排法，才能使每次投入大海的都是非教徒。
*问题分析与算法设计
约瑟夫问题并不难，但求解的方法很多；题目的变化形式也很多。这里给出一种实现方法。
题目中30个人围成一圈，因而启发我们用一个循环的链来表示，可以使用结构数组来构成一个循环链。结构中有两个成员，其一为指向下一个人的指针，以构成环形的链；其二为该人是否被扔下海的标记，为1表示还在船上。从第一个人开始对还未扔下海的人进行计数，每数到9时，将结构中的标记改为0，表示该人已被扔下海了。这样循环计数直到有15个人被扔下海为止。

使用PHP实现
```
<?php

$people = array('1', '2', '3', '4', '5', '6');
$n = count($people);
$k = 1;
$m = 5;
$p = $k%$n; //开始报数的那个人的编号

$i = 0; //循环计数器
$j = 0; //报数计数器
$out = array();
while($n = count($people)) {
    if ( $n == 1 ) {
        $out[] = current($people);
        break;
    }
    $i++;
    $name = current($people);

    //开始报数
    if ( $i >= $p ) {
        $j++;
        if ( $j == $m ) {
            $j = 0;
            $out[] = $name;
            unset($people[key($people)]);
            //delete array value,pointer move to next address automatically.
            prev($people);
        }

    }
    if ( next($people) === false ) {
        reset($people);
    }
}
var_dump($out);
```
2015-05-12

分类： algorithm

TOTP算法

斐波那契数列算法

使用PHP计算约瑟夫问题