A method which improves the security of the authentication between two entities in a telecommunication network, and particularly between a mobile terminal and the fixed network, notably visitor location and nominal recorders and an authentication center, in a cellular radiotelephony network. Prior to a first authentication of the terminal, and more precisely of the SIM card therein, by the fixed network, a second authentication is based on an algorithm in which there are entered a random number produced and transmitted by the fixed network and a key different from the key for the first authentication. A transmitted signature and a signature result are produced by the fixed network and the terminal, and compared in the terminal in order to enable the first authentication in the event of equality.