How to install php7.1-intl extension for PHP7.1

Hello ! I am trying to install the intl extension for php 7.1 to use it to build my PHP project and test it. Stack is only PHP.
However when I try sudo apt-get install php7.1-intl it cannot find the package.

Here is my latest failed build https://circleci.com/gh/matks/ApiCycle/23 :

sudo apt-get install php7.1 php7.1-intl

Reading package lists... 1%
Reading package lists... 67%
Reading package lists... Done


Building dependency tree       


Reading state information... Done

E: Unable to locate package php7.1
E: Couldn't find any package by regex 'php7.1'
E: Unable to locate package php7.1-intl
E: Couldn't find any package by regex 'php7.1-intl'
Exited with code 100

Here is when I try to do it using SSH:

$ sudo apt-get install php7.1-intl
Reading package lists... Done
Building dependency tree
Reading state information... Done
E: Unable to locate package php7.1-intl
E: Couldn't find any package by regex 'php7.1-intl'

Here is my config.yml (this is a public github repo):

There is a topic which has the solution for php7.0 (How to install php7.0-intl extension for PHP7.0) but the solution does not work for php7.1

Have you tried apt-cache search php7.0-intl on this box to see if the underlying distro is recent enough to include PHP 7.1?

You can run a build with the SSH option, let it fail, and then SSH in and run this command.

I have tried and apt-cache could not find the package.

I am currently actively learning to use Docker in order to build my own custom image to run my tests. If I succeed, I will post here my solution so it might help others.